Counting Techniques

Suppose you have 2 shirts and 3 ties; how many outfits could you wear?  Just by constructing a tree we can see that the answer is 2∙3=6.  However, if the numbers were large (many shirts and many ties), constructing a tree would be impractical.  Hence we need a rule that allows us to determine the number of outfits quickly.  The fundamental principle of counting tells us that

If a procedure can be performed in m ways, and after that a second procedure can be performed in n ways, etc., then the number of ways the procedures can be performed is

 m ∙ n ∙ ... 

Each outfit is obtained by two procedures, namely choosing a shirt and choosing a tie.  The former can be done in 2 ways (2 shirts) and the latter in 3 (3 ties).  Hence, the number of possible outfits is 3∙2=6.  Alternatively, think of an outfit as a two-slot thing: the first slot to be filled in 2 ways by shirts and the second in 3 ways by ties.    

Example

How many 3 letter words can be produced in English?  Here, we can think of each word as made up of 3 slots each of which can be filled by one of 26 letters, as repetitions are allowed.  (Letter A, for example, can appear in more than one slot).  Hence, there are 26∙26∙26 = 26³ =17,576 possible words.  Note that if we do not allow repetitions, there are 26 ways of filling the first slot, 25 of filling the second, and 24 of filling the third, so that the number of words will be 26 ∙ 25 ∙ 24 = 15,600.

Example

A license plate consists of 3 letters followed by 3 digits.  Repetitions are allowed in the letters but not in the digits.  How many different plates can be made?  Here there are 6 slots; the first 3 can each be filled in 26 ways and the last 3 in 10, 9, and 8 ways (no repetitions here).  Hence, the number sought is 26³ ∙ 10 ∙ 9 ∙ 8 = 12,654,720.

Permutations (Lineups)

An ordered arrangement of r objects out of n objects is an r-permutation, and it is represented by P(n,r).  For example, if we have 3 objects, a, b, and c, then  a,b,c is a permutation.  Permutations are like lineups: order matters in that lineup a,b,c is different from lineup b,a,c.  Think of a 2-permutation out of 3 objects as a lineup with 2 positions (slots).  If you have 3 objects, the number P(3,2) of 2-permutations is easily obtained: there are 3 ways of filling the first slot and 2 of filling the second (as one of the three is already used in the first slot); hence, the fundamental principle of counting tells us that P(3,2) = 6.

In general, it can be shown that

P(n,r) = n!/(n-r)!                                                                                     (1)

Note that

P(n,n) = n!.                                                                                                  (2)

In other words, there are n! n-permutations of n objects.

Example

In how many ways can 5 persons arrange themselves in a row?  In other words, how many lineups can 5 persons form?  By (2), P(5,5)= 5! = 120.

Example

If there are 6 persons, in how many ways can 4 of them be arranged?  That is, how many 4-persons lineups can be made out of 6 persons?  Here we apply (1), so that P(6,4) = 6!/2! = 360.

Combinations (Committees)

Combinations are like committees, that is, lineups in which, as it were, the order does not matter.  So, a committee made up of a,b is the same committee as one made up of b,a.  The number of combinations of r objects out of n objects is denoted by C(n,r) and we can obtain it if we think a bit.  Let us start with permutations (lineups).  We know that

P(n,r) = n!/(n-r)!.

However, (2) tells us that to a combination (committee) of r members there correspond r! permutations (lineups); in other words, r objects allow r! permutations.  Hence,

C(n,r) = P(n,r)/r! =  n!/r!(n-r)!,                                                                    (3)

which is what we want.  Note that often instead of the symbol C(n,r) the symbol (ⁿ_r) is used.

Example

How many 3 member committees can be made out of 7 persons?   By (3),

C(7,3) = 7!/[3!(7-3)!] = 7!/(3!4!) = 35.

Example

How many poker hands are possible out of a 52 card deck?  A poker hand is a combination (a committee) of 5 members out of 52.  Hence, C(52,5) = 52!/(5!47!).

Example

How many poker hands with a king of hearts are possible?  A hand with a king of hearts is a committee of 5 members in which, however, as seat is permanently occupied by the king of hearts.  Hence, what we really want to know is how many 4-member committees can be made out of 51 cards (the deck minus the king of hearts).  So,

C(51,4) = 51!/(4!47!).

 

Calculating some probabilities

We can now use counting techniques to determine probabilities that are more numerically complex than those readily solvable using trees.

Example

A committee of 5 is chosen from M₁,..., M₉.  What's the probability that M₉ is a member of the committee?  As with the poker hand with the king of hearts, the number of committees with M₉ as a member is

C(8,4) = 8!/(4!4!) = (5∙6∙7∙8)/(4∙3∙2) = 70.

The total number of 5 persons committees is C(9,5) = 9!/(5!4!) =  (6∙7∙8∙9)/(4∙3∙2) = 126.  Hence, Pr(M₉ is a member of the committee) = 70/126.

Example

Five men at the opera check their coats.  What's the probability that each will get his own coat if the coats are returned randomly?  Here, think of lining up the five men and of lining up the five coats.  There are P(5,5) coat lineups, only one of which associates each men with his own coat.  Hence, Pr(each men gets his own coat) = 1/5! = 1/120.

Example

What's the probability of a poker hand with no spades?  As spades make up ¼ of the deck, there are C(39,5) poker hands with no spades.  Given that there are C(52,5) poker hands, Pr(a poker hand with no spades) = C(39,5)/C(52,5).