combinatorial analysis

The Fundamental Counting Principles

1. Multiplication counting principle

If a first operation can be done n1 different ways, the second 
n2 different ways, ..., the kth nk different ways; then the whole 
operation (all the operations) can be done 
n1 x n2 x ... x nk differents ways.


Example:
Question 1.
How many passwords can be set if each one must have two letters 
and three digits? for instance aa123
The repetition is permitted.

Answer:
We have 26 possibilities to choose the first letter, and
26 possibilities to choose the second letter.

10 possibilities to choose the first digit
10 possibilities to choose the second letter,
10 possibilities to choose the third letter.

The total number of possibilities is:
26 x 26 x 10 x 10 x 10 = 676 000 passwords.

Question2: 
What about if the repetition is not permitted and the 
letters must different from "a" and digits different 
from "0"?
Answer:
In this case:
We have 25 possibilities to choose the first letter, and
24 possibilities to choose the second letter.

9 possibilities to choose the first digit
8 possibilities to choose the second letter,
7 possibilities to choose the third letter.

The total number of possibilities is:
25 x 24 x 9 x 8  x 7 = 302400 ways to set a password.

2. Addition counting principle

If a first operation can be done n1 different ways, the second 
n2 different ways, ..., the kth nk different ways; then the number 
of ways to make one OR another  operation is: 
n1 + n2 + ... + nk different ways. 
Remark the disjunction "OR". 
The operations are mutually exclusive.


Example:
Question1  
We offer 30 books of Science, 20 of Litterature, and 10 of Music in a 
three different bookstores. How many choices do we have if we can get 
only one book of each category from each bookstore?

Answer:
The bookstores are independent, and the operations "get a book" are 
mutually exclusive. 
We have then 30 choices for Science, 20 for litterature,and 10 for Music. 
The total is 30 + 20 + 10 = 60 choices.

Question 2 
Waht about if we can get five (5) books. Three of science, two of Music, 
and only one (as before) book of Litterature?

Answer:
In this case, we have C(3,30) + C(2,20) + C(1,10)
C(n,m) is the combination of n among m (n choices among m books).
The result is then: 30!/3!(30 - 3)! + 20!/2!(20 - 2)! + 10!/1!(10 - 1)! = 
28 x 29 x 30/6 + 19 x 20/2 + 10 = 4060 + 190 + 10 = 4260 choices.