6.042/18.062J Mathematics for Computer Science April 6,2005
Srini Devadas and Eric Lehman
Notes for Recitation 15
Problem 1,Learning to count takes practice!
(a) In how many different ways can Blockbuster arrange 64 copies of 13 conversations
about one thing,96 copies of L’Auberge Espagnole and 1 copy of Matrix Revolutions on
a shelf? What if they are to be arranged in 5 shelves?
Solution,For 1 shelf,this is the number of ways to arrange 64 C’s,96 A’s,and 1 M,
By the bookeeper rule,
(64 + 96 + 1)!
64! 96! 1!
For 5 shelves,we can do the simple trick of introducing the dividers between the
shelves as new objects,That is,we want the number of ways to arrange 64 C’s,96
A’s,1 M,and 4 X’s (dividers),By the bookeeper theorem,again,
(64 + 96 + 1 + 4)!
64! 96! 1! 4!
(b) Find the number of 5-card hands with exactly three aces,
Solution,We can choose the three aces in
4
ways,and we can choose the remain-
?
3

4 48
ing two cards in
48
ways,Thus,there are such hands,
2 3 2
(c) Find the number of 5-card hands in which every suit appears at most twice,
Solution,There are two cases,Either one suit appears twice or else two suits appear
twice,The number of hands in which one suit appears twice is
13
13
3
4,since there

2
· ·
are 4 ways to choose the doubly-represented suit,
13
ways to choose two values
2
from this suit,and 13
3
ways to choose values for cards in the three remaining suits,

2
4
Similarly,the number of hands in which two suits appear twice is
13
13 ·
2
2.
2
· ·
Therefore,there are a total of

2

13 13 4
13
3
4 + 13 · 2
2
· ·
2
·
2
·
such hands,
(d) In how many ways can 20 indistinguishable pre-frosh be stored in four different
crates if each crate must contain an even number of pre-frosh?
Solution,There is a bijection from 13-bit strings with exactly 3 ones,In particular,
the string 0
a
10
b
10
c
10
d
corresponds to to storing 2a prefrosh in the?rst crate,2b in the

2 Recitation 15
second,2c in the third,and 2d in the fourth,Therefore,the number of ways to store
the pre-frosh is equal to the number of 13-bit strings with exactly 3 ones,which is
13
.
3
(e) How many paths are there from point (0,0) to (50,50) if every step increments
one coordinate and leaves the other unchanged and there are impassable boulders
sitting at points (10,10) and (20,20)?
Solution,We use inclusion-exclusion,The total number of paths is
100
,but we

50
80
must subtract off the obstructed paths,There are
20
paths through the?rst

10
·
40

20
boulder,since there are
10
paths from the start to the boulder and
80
paths from

40
60
the boulder to the?nish,Similarly,there are
40
paths through the second
20 30
·
boulder,However,we must subtract off paths going through both boulders,and
20 60
there are
20
of those,Therefore,the total number of paths is,
10 10 30
· ·
100 20 80 40 60 20 20 60
+
50
10
·
40
20
·
30 10
·
10
·
30
(f) In how many ways can the 72 students in 6.042 be divided into 18 groups of 4?
Solution,There is a 18!-to-1 mapping from sequences containing four 1’s,four 2’s,
.,,,and four 18’s,Speci?cally,the sequence (t
1
,...,t
72
) corresponds to the assign-
ment where each student i is placed in group t
i
,The mapping is 18!-to-1,because
we can permute the team numbers (in 18! different ways) without altering the way
the class is partitioned,Therefore,the number we want is
72!
(4!)
18
18!
by the bookeeper rule and the division rule,
(g) Set A has r elements and set B has n elements,How many functions are there
from A to B? How many of them are injective (one-to-one)? How many of them are
bijective?
Solution,Say A = {a
1
,...,a
r
} and B = {b
1
,...,b
n
} and consider the mapping that
sends every function f, A B to the sequence (f(a
1
),...,f(a
r
)),This is a bijection →
between functions from A to B and r-long sequences of elements from B,By the
product rule,the number of such sequences is
r
n = n,n·

n···
r times
For injections,?rst note that (by the pigeonhole principle) there is no way to inject
A into B if B has fewer elements than A,That is,if r > n,then the number of
injections from A to B is 0,If r ≤ n,though,the same mapping as previously

3 Recitation 15
becomes a bijection between injections from A to B and r-long sequences of distinct
elements from B,By the generalized product rule,the number of such sequences is
n!
n · (n? 1) · (n? 2) ···(n?r + 1) =
(n?r)!
,
that is,the number of r-permutations of n elements,
For bijections,we similarly note that in the case r =? n the number of bijections from
A to B is 0,If r = n,then a function from A to B is a bijection iff it is an injection,So
the number of bijections equals the number of injections,n!/(n? n)! = n!,which is
exactly the number of different permutations of n elements,
Notice how functions,injections,and bijections correspond respectively to sequences,
r-permutations,and permutations,
Problem 2,A pizza house is having a promotional sale,Their commercial reads,
We offer 9 different toppings for your pizza! Buy 3 large pizzas at the regular
price,and you can order each one with any combination of toppings abso-
lutely free,That’s 22,369,621 different ways to design your order!
The ad writer was a former Harvard student who had evaluated the formula (2
9
)
3
/3! on
her calculator and gotten close to 22,369,621,Unfortunately,(2
9
)
3
/3! is obviously not an
integer,so clearly something is wrong,What? In particular,did she overcount or did she
undercount? What is the correct number?
Solution,The number of ways to choose different toppings for one pizza is the number
of the possible subsets of the set of 9 toppings,namely,2
9
,The ad writer presumably then
gured out that there were (2
9
)
3
ways to place a sequence of three pizza orders,Then she
probably reasoned that each set of three orders arises from 3! sequences,so the Division
Rule would imply that the number of orders is (2
9
)
3
/3!,
It’s true that every set of three different orders arises from 3! different sequences of
three orders,The bug is that if some of the three orders are the same,then the set of
three orders arises from fewer than 3! sequences,For example,if all three pizzas have
the same toppings,there is only one sequence of orders for them,So dividing by 3! will
undercount,
We really need to count the number of ways to,throw” three indistinguishable balls
(the three orders) into 2
9
distinguishable bins (the different toppings),Hence,there is a
bijection to the number of (2
9
+ 2)-bit strings with exactly 2
9
1 ones and 3 zeros,
2
9
+ 2 2
9
+ 2
= = 22,500,864,
2
9
1 3

4 Recitation 15
Combinatorial proofs of identities
Recall the basic plan for a combinatorial proof of an identity x = y,
1,De?ne a set S,
2,Show that |S| = x by counting one way,
3,Show that |S| = y by counting another way,
4,Conclude that x = y,
Problem 3,You want to choose a team of m people from a pool of n people for your
startup company,and from these m people you want to choose k to be the team managers,
You took 6.042,so you know you can do this in
n m
m k
ways,But your CFO,who went to Harvard Business School,comes up with the formula
n n? k
,
k m? k
Before doing the reasonable thing —dump on your CFO or Harvard Business School—
you decide to check his answer against yours,
(a) Start by giving an algebraic proof that your CFO’s formula agrees with yours,
Solution,

n m n! m!
=
m k m!(n? m)! k!(m? k)!
n!
=
(n? m)!k!(m? k)!
=
n!(n? k)!
(n? m)!k!(m? k)!(n? k)!
=
n! (n? k)!
k!(n? k)! (n? m)!(m? k)!
n! (n? k)!
=
k!(n? k)! ((n? k)? (m? k))!(m? k)!
n n? k
=,
k m? k


5 Recitation 15
(b) Now give a combinatorial argument proving this same fact,
Solution,Instead of choosing?rst m from n and then k from m,you could alter-
nately choose the k managers from the n people and then choose m? k people to?ll
n
out the team from the remaining n? k people,This gives you
n? k
ways
k m? k
of picking your team,Since you must have the same number of options regardless
of the order in which you choose to pick team members and managers,
n m n n? k
= ,
m k k m? k
Problem 4,Now try the following,more interesting theorem,
n

n2
n?1
= k
n
k
k=1
(a) Start with a combinatorial argument,Hint,let S be the set of all sequences in
containing exactly one?.{0,1,?}
n
n
Solution. Let S be the set of all sequences in {0,1,?} containing exactly one?,
On one hand,|S| = n2
n?1
,since the? can appear in n positions and there are 2
n?1
settings for the remaining symbols,
On the other hand,every sequence in S contains between 1 and n nonzero entries
since the?,at least,is nonzero,The number of sequences in S with exactly k nonzero
n n
entries is k,since there are
k
ways to select the positions of the nonzero entries
k
and then k ways to select one of those entries to be the?,Thus,by the Sum Rule,
n

n
S = k
k
| |
k=1
Equating these two expressions for |S| proves the theorem,
(b) How would you prove it algebraically?
6 Recitation 15
Solution,We calculate,
n
n
n
n!
k = k
k=1
k
k=1
k!(n? k)!
n
n!
=
k=1
(k? 1)!(n? k)!
=
n
n
(n? 1)!
k=1
(k? 1)!((n? 1)? (k? 1))!
= n
n?1
(n? 1)!
j=0
j!((n? 1)? j)!
= n
n?1
n? 1
j=0
j
= n2
n?1
The?rst three steps are algebra,replacing the binomial coef?cient with its ratio of
factorials,then simplifying k,then trying to form another coef?cient by drawing n
out of n! (and eventually out of the sum),In the fourth step,we change variables,
from k to j = k? 1,In the?fth step,we recognize the new coef?cient we were after,
The?nal step uses the binomial theorem,