Combinatorics
Probability & Statistics
© The scientific sentence. 2010
|
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.
|
|
|