Introduction

n

Chapter 2: Combinatorial Analysis

I. Definition Combinatorial analysis is the mathematical theory of counting.

II. Prinipe fundamental thorem of counting Let A1 , A2 , ... , Ak be k set s sets of cardinals n1 , n2 ,... , nk

respectively. Then, the number of ways to choose one element from each set is: n1× n2×….×nk

Example: If we want to buy a computer system consisting of three components: a computer, a monitor, and a printer,

and we have three brands of computers, two brands of monitors, and four brands of printers, then the total number of

different systems we can buy is: 3×2×4=24

Thus, we have 24 possible configurations for the three components.

Notably, we distinguish three types of configurations: arrangements, permutations, and combinations.

I. Arrangements

a) Arrangements without repetition: An arrangement without repetition is any ordered selection of k elements chosen

from n elements without replacement. The number of such arrangements is given by

��

� = �!

(�−�)!

Examples:

1) The number of five-letter words (with or without meaning) that can be formed using the 26 letters

of the alphabet corresponds to the number of arrangements without repetition with k =5, n=26 .

2) The number of committees (president, secretary, treasurer) of three members that can be formed from

a group of eight people corresponds to the number of arrangements without repetition with k =3, n=8.

3) A DNA sequence consists of a chain of four nucleotides [Adenine, Cytosine, Guanine and Thymine].

The number of possible arrangements of two nucleotides (dinucleotides) with k =2, n=4.

b) Arrangements with repetition: An arrangement with repetition is an ordered selection of k elements chosen from n

elements with replacement. The number of such arrangements is:

�