102 TECHNIQUES OF COUNTING [CHAP. 5
Now the term in the product which containsbris obtained fromb[(nr− 1 )an−r+^1 br−^1 ]+a[(nr)an−rbr]=(nr− 1 )an−r+^1 br+(nr)an−r+^1 br
=[(nr− 1 )+(nr)]an−r+^1 brBut, by Theorem 5.3,(
n
r− 1)
=(
n
r)
=(
n+ 1
r). Thus, the term containingbris:
(
n+ 1
r)
an−r+^1 brNote that(a+b)(a+b)nis a polynomial of degreen+1inb. Consequently:(a+b)n+^1 =(a+b)(a+b)n=∑n+^1r= 0(
n+ 1
r)
an−r+^1 brwhich was to be proved.5.29. Letnandn 1 ,n 2 ,...,nrbe nonnegative integers such thatn 1 +n 2 +···+nr=n. Themultinomial
coefficientsare denoted and defined by:
(
n
n 1 ,n 2 ,...,nr)
=n!
n 1 !n 2 !...nr!Compute the following multinomial coefficients:(a)(
6
3 , 2 , 1)
;(b)(
8
4 , 2 , 2 , 0)
;(c)(
10
5 , 3 , 2 , 2)
.(a)(
6
3 , 2 , 1)
=
6!
3! 2! 1!
=
6 · 5 · 4 · 3 · 2 · 1
3 · 2 · 1 · 2 · 1 · 1
= 60(b)(
8
4 , 2 , 2 , 0)
=8!
4! 2! 2! 0!
=8 · 7 · 6 · 5 · 4 · 3 · 2 · 1
4 · 3 · 2 · 1 · 2 · 1 · 2 · 1 · 1
= 420(c)(
10
5 , 3 , 2 , 2)
has no meaning, since 5+ 3 + 2 + 2 =10.5.30. Astudent must take five classes from three areas of study. Numerous classes are offered in each discipline,
but the student cannot take more than two classes in any given area.(a) Using the pigeonhole principle, show that the student will take at least two classes in one area.(b) Using the Inclusion–Exclusion Principle, show that the student will have to take at least one class in
each area.
(a) The three areas are the pigeonholes and the student must take five classes (pigeons). Hence, the student must
take at least two classes in one area.(b) Let each of the three areas of study represent three disjoint sets,A,B, andC. Since the sets are disjoint,
m(A∪B∪C)= 5 =n(A)+n(B)+n(C). Since the student can take at most two classes in any area of study, the
sum of classes in any two sets, sayAandB, must be less than or equal to four. Hence, 5−[n(A)+n(B)]=
n(C)≥1. Thus, the student must take at least one class in any area.