Advanced book on Mathematics Olympiad

760 Combinatorics and Probability

elect the president and then elect the other members of the committee from the remaining
2 n−1 people.

881.We will prove that both terms of the equality count the same thing. To this end, we
introduce two disjoint setsMandNcontainingm, respectively,nelements.
For the left-hand side, choose firstkelements inM. This can be done in

(m

k

)

ways.
Now add thesekelements toNand choosemelements from the newly obtained set. The
number of ordered pairs of sets(X, Y )withX⊂M,Y⊂N∪X,|X|=k, and|Y|=m
is equal to

(m

k

)(n+k

m

)

. Varyingk, we obtain, for the total number of pairs(X, Y ),
n− 21
∑

k=m

(

n

2 k+ 1

)(

k

m

)

.

The same problem can be solved differently, namely choosingYfirst. If we fix the
cardinality ofY∩N, say|Y∩N|=j,0≤j≤m, then|Y∩M|=m−j, and so
there are

(n

j

)(m

m−j

)

ways to chooseY. NowXcontains the setY∩M, the union with
some (arbitrary) subset ofM\Y. There arejelements inM\Y, so there are 2jpossible
choices forX. Consequently, the number of pairs with the desired property is

∑m

j= 0

(

n

j

)(

m

j

)

2 j.

Setting the two numbers equal yields the identity from the statement.
(I. Tomescu,Problems in Combinatorics, Wiley, 1985)

882.We prove the identity by counting, in two different ways, the cardinality of the set of
words of lengthnusing the alphabet{A, B, C}and satisfying the condition that precisely
kof the letters areA, and all of the lettersBmust be among the firstmletters as read
from the left.
The first count is according to the number ofB’s. PlacemsymbolsXin a row and
following themn−msymbolsY:

XX...XX︸ ︷︷ ︸

m

YY ...YY︸ ︷︷ ︸

n−m

.

Chooseiof theX’s (in

(m

i

)

ways), and replace them byB’s. Choosekof then−i
remaining symbols (in

(n−i

k

)

ways), and replace them byA’s. Any remainingX’s orY’s
are now replaced byC’s. We have constructed

(m

i

)(n−i

k

)

words satisfying the conditions.
Summing overi, we have the sum on the left.
The second count is according to the number ofA’s among the firstmletters of the
word. We start with the same sequence ofX’s andY’s as before. Chooseiof themX’s
(in

(m

i

)

ways), replace each of them byAand replace each of the otherm−iX’s byB