Page 10 - 4660

Combinatorial Analysis

Example 1.7. A standard deck of playing cards consists of 52 cards. How many
five-card hands can be chosen from this deck? ,

5
52!
Solution. We have N = C 55 = 5!(52−5)! = 55·54·53·52·51 = 2598960. There are 2598960 five-cards
1·2·3·4·5
hands.
Example 1.8. Using (1.8) we have

2 2 2
4
4 4 0
4 3 1
3
2 2
3
4
3
4 0 4
3
4
(x + y) = C x y + C x y + C x y + C xy + C x y = x + 4x y + 6x y + 4xy + y .
0 1 4 4 4
The following formulas are valid
1
0
n
n
1. C + C + . . . + C = 2 (consequence of the Newton binomial formula).
n
n
n
2. C m = C n−m (symmetry property).
n n
n
1
3. C = 1, C = n.
n n
m+1
m
4. C + C n m+1 = C n+1 , where 0 ≤ m ≤ n (a recurrent formula).
n
Another useful result that may be derived using the binomial coefficients is the number of
ways in which n distinguishable objects can be divided into m piles, with n i objects in the i-th
pile, i = 1, 2, . . . , m (the ordering of objects within each pile being unimportant). This may be
straightforwardly computed as follows. We may choose the n 1 objects in the first pile from the
original n objects in C n 1 ways. The n 2 objects in the second pile can then be chosen from the
n
n − n 1 remaining objects in C n 2 ways, etc. We may continue in this fashion until we reach the
n−n 1
(m − 1)-th pile, which may be formed in C n m−1 ways. The remaining objects then form
n−n 1 −...−n m−2
the m-th pile and so can only be ’chosen’ in one way. Thus the total number of ways of dividing
the original n objects into m piles is given by the product
n 1
N = C C n 2 . . . C n m−1 =
n n−n 1 n−n 1 −···−n m−2
n! (n − n 1 )! (n − n 1 − n 2 − · · · − n m−2 )!
= · · · =
n 1 !(n − n 1 )! n 2 !(n − n 1 − n 2 )! n m−1 !(n − n 1 − n 2 − · · · − n m−2 − n m−1 )!
n! (n − n 1 )! (n − n 1 − n 2 − · · · − n m−2 )! n!
= · · · = . (1.10)
n 1 !(n − n 1 )! n 2 !(n − n 1 − n 2 )! n m−1 !n m ! n 1 !n 2 ! · · · n m !
n 1 n 2
Thesenumbersarecalledmultinomial coefficientssince(1.10)isthecoefficientofx x · · · x n m
1
2
m
n
in the multinomial expansion of (x 1 + x 2 + · · · + x m ) , i.e. for positive integer n
∑ n!
n
(x 1 + x 2 + · · · + x m ) = x x · · · x n m .
n 1 n 2
n 1 !n 2 ! · · · n m ! 1 2 m
n 1 ,n 2 ,...,n m
n 1 +n 2 +···+n m=n
k
For the case m = 2, n 1 = k, n 2 = n−k, (1.10) reduces to the binomial coefficient C . Furthermore,
n
we note that the multinomial coefficient (1.10) is identical to the expression (1.3) for the number
of distinguishable permutations of n objects, n i of which are identical and of type i (for i = 1, 2,
. . . , m and n 1 + n 2 + · · · + n m = n). A few moments’ thought should convince the reader that the
two expressions (1.10) and (1.3) must be identical.
Example 1.9. In the card game of bridge, each of four players is dealt 13 cards
from a full pack of 52. What is the probability that each player is dealt an ace?,

10