206 CHAPTER 6 COMBINATORICS
integer? For example,
4=1+3=3+1=2+2=1+1+2
= 1 +2+ 1 = 2+ 1 + 1= 1 + I + 1 + I,so when n = 4, there are eight such ordered partitions.
6.2.20 Ten dogs encounter eight biscuits. Dogs do
not share biscuits! Verify that the number of different
ways that the biscuits can be consumed will equal
(a) (�) if we assume that the dogs are distinguish
able, but the biscuits are not;
(b) 108 if we assume that the dogs and the biscuits
are distinguishable (for example, each biscuit is
a different flavor).
6.2.2 1 In Problem 6.2.20 above, what would the an
swer be if we assume that neither dogs nor biscuits are
distinguishable? (The answer is not I!)
6.2.22 When (x + y + z)^1999 is expanded and like
terms are collected, how many terms will there be?
[For example, (x+ y)^2 has three terms after expansion
and simplification.]
6.2.23 Find a formula for the number of different or
dered triples (a, b, c) of positive integers that satisfy
a+b+c = n.
6.2.24 Let S be a set with n elements. In how
many different ways can one select two not neces
sarily distinct or disjoint subsets of S so that the
union of the two subsets is S? The order of selec
tion does not matter; for example, the pair of sub
sets {a,c}, {b,c,d,e,J} represents the same selection
as the pair {b,c,d,e,J}, {a,c}.
6.2.25 (AIME 1988) In an office, at various times dur
ing the day, the boss gives the secretary a letter to type,
each time putting the letter on top of the pile in the sec
retary's in-box. When there is time, the secretary takes
the top letter off the pile and types it. There are nine
letters to be typed during the day, and the boss delivers
them in the order 1,2,3,4,5,6,7, 8,9.
While leaving for lunch, the secretary tells a col
league that letter 8 has already been typed, but says
nothing else about the morning's typing. The col
league wonders which of the nine letters remain to be
typed after lunch and in what order they will be typed.
Based upon the above information, how many such
after-lunch typing orders are possible? (That there are
no letters left to be typed is one of the possibilities.)
6.2.26 (AlMEI983) A gardener plants three mapletrees, four oak trees and five birch trees in a row. He
plants them in random order, each arrangement being
equally likely. Find the probability that no two birch
trees are next to one another.
6.2.27 (AIME 1983) Twenty-five people sit around a
circular table. Three of them are chosen randomly.
What is the probability that at least two of the three
are sitting next to one another?
6.2.28 We are given n points arranged around a cir
cle and the chords connecting each pair of points are
drawn. If no three chords meet in a point, how many
points of intersection are there? For example, when
n = 6, there are 15 intersections.6.2.29 Given g girls and b boys, how many different
ways can you seat these people in a row of g + b seats
so that no two boys sit together? There are two differ
ent interpretations: one where you do not distinguish
among individual girls and between individual boys
(i.e., you would not consider the seating arrangements
"Becky, Sam, Amy, Tony" and "Amy, Tony, Becky,
Sam" as different), and one where you do distinguish
among individuals. Answer the question for each in
terpretation. Find a general formula, and prove why
your formula is correct.
6.2.30 The balls in urns formula says that if you are
order h hats from a store that sells k different kinds of
hats, then there are (
k +
: -
I
) different possible or
ders. Use a partitioning argument to show that this isalso equal to
rtl C) C = :).6.2.31 Use a combinatorial argument to show that for
all positive integers n,m,k with n and m greater than
or equal to k,{. (�) ( m.
)=
(n+m)
.
�o } k-} k
This is known as the Vandermonde convolution for
mula.