6.042/18.062J Mathematics for Computer Science April 5,2005
Srini Devadas and Eric Lehman Lecture Notes
Counting III
Today we’ll brie?y review some facts you dervied in recitation on Friday and then turn
to some applications of counting,
1 The Bookkeeper Rule
In recitation you learned that the number of ways to rearrange the letters in the word
BOOKKEEPER is,
total letters
10!
1! 2! 2! 3! 1! 1!
B’s O’s K’s E’s P’s R’s
This is a special case of an exceptionally useful counting principle,
Rule 1 (Bookkeeper Rule),The number of sequences with n
1
copies of l
1
,n
2
copies of l
2
,.,,,
and n
k
copies of l
k
is
(n
1
+ n
2
+,.,+ n
k
)!
n
1
! n
2
!,.,n
k
!
provided l
1
,...,l
k
are distinct,
Let’s review some applications and implications of the Bookkeeper Rule,
1.1 20-Mile Walks
I’m planning a 20 miles walk,which should include 5 northward miles,5 eastward miles,
5 southward miles,and 5 westward miles,How many different walks are possible?
There is a bijection between such walks and sequences with 5 N’s,5 E’s,5 S’s,and 5
W’s,By the Bookkeeper Rule,the number of such sequences is,
20!
5!
4
?
?
?
2 Counting III
1.2 Bit Sequences
How many n-bit sequences contain exactly k ones?
Each such sequence also contains n? k zeroes,so there are
n!
k! (n? k)!
by the Bookkeeper Rule,
1.3 k-element Subsets of an n-element Set
How many k-elements subsets of an n-element set are there? This question arises all the
time in various guises,
In how many ways can I select 5 books from my collection of 100 to bring on vaca-
tion?
How many different 13-card Bridge hands can be dealt from a 52-card deck?
In how many ways can I select 5 toppings for my pizza if there are 14 available?
There is a natural bijection between k-element subsets of an n-element set and n-bit
sequences with exactly k ones,For example,here is a 3-element subset of {x
1
,x
2
,...,x
8
}
and the associated 8-bit sequence with exactly 3 ones,
x
1
,x
4
,x
5
}{
( 1,0,0,1,1,0,0,0 )
Therefore,the answer to this problem is the same as the answer to the earlier question
about bit sequences,
Rule 2 (Subset Rule),The number of k-element subsets of an n-element set is,
n! n
=
k! (n? k)! k
The factorial expression in the Subset Rule comes up so often that there is a shorthand,
,This is read,n choose k” since it denotes the number of ways to choose k items from
among n,We can immediately knock off all three questions above using the Sum Rule,
I can select 5 books from 100 in
100
ways.
5
There are
52
different Bridge hands,
13
n
k
Counting III 3
There are
14
different 5-topping pizzas,if 14 toppings are available,
5
The k-element subsets of an n-element set are sometimes called k-combinations,There
are a great many similar-sounding terms,permutations,r-permutations,permutations
with repetition,combinations with repetition,permutations with indistinguishable ob-
jects,and so on,For example,the Bookkeeper Rule is sometimes called the,formula for
permutations with indistinguishable objects”,Broadly speaking,permutations concern se-
quences and combinations concern subsets,However,the counting rules we’ve taught you
are suf?cient to solve all these sorts of problems without knowing this jargon,so we’ll
skip it,
1.4 Word of Caution
Someday you might refer to the Bookkeeper Rule in front of a roomful of colleagues and
discover that they’re all staring back at you blankly,This is not because they’re dumb,
but rather because we just made up the name,Bookkeeper Rule”,However,the rule is
excellent and the name is apt,so we suggest that you play through:,You know? The
Bookkeeper Rule? Don’t you guys know anything”
2 Binomial Theorem
Counting gives insight into one of the basic theorems of algebra,A binomial is a sum of
two terms,such as a + b,Now let’s consider a postive,integral power of a binomial,
(a + b)
n
Suppose we multiply out this expression completely for,say,n = 4,
(a + b)
4
= aaaa + aaab + aaba + aabb
+ abaa + abab + abba + abbb
+ baaa + baab + baba + babb
+ bbaa + bbab + bbba + bbbb
Notice that there is one term for every sequence of a’s and b’s,Therefore,the number of
terms with k copies of b and n? k copies of a is,
n! n
=
k! (n? k)! k
by the Bookkeeper Rule,Now let’s group equivalent terms,such as aaab = aaba = abaa =
n
baaa,Then the coef?cient of a
n?k
b
k
is, So for n = 4,this means,
k
4 4 4 4 4
4
b
0 2
b
2 1
b
3 0
b
4
(a + b)
4
= a + a
3
b
1
+ a + a + a
0
·
1
·
2
·
3
·
4
·
In general,this reasoning gives the Binomial Theorem,
4 Counting III
Theorem 1 (Binomial Theorem),For all n ∈ N and a,b ∈ R,
n
n
n?k
b
k
(a + b)
n
= a
k
k=0
n
The expression is often called a,binomial coef?cient” in honor of its appearance here,
k
This reasoning about binomials extends nicely to multinomials,which are sums of two
or more terms,For example,suppose we wanted the coef?cient of
3
bo
2
k
2
e pr
in the expansion of (b+ o+ k + e+ p+ r)
10
,Each term in this expansion is a product of 10
3
variables where each variable is one of b,o,k,e,p,or r,Now,the coef?cient of bo
2
k
2
e pr is
the number of those terms with exactly 1 b,2 o’s,2 k’s,3 e’s,1 p,and 1 r,And the number
of such terms is precisely the number of rearrangments of the word BOOKKEEPER,
10! 10
=
1! 2! 2! 3! 1! 1! 1,2,2,3,1,1
The expression on the left is an example of a,multinomial coef?cient” and the notation
on the right is a shorthand,This reasoning extends to a general theorem,
Theorem 2 (Multinomial Theorem),For all n ∈ N and z
1
,...z
m
∈ R,
(z
1
+ z
2
+,.,+ z
m
)
n
=
n
z
1
k
1
z
2
k
2
...z
k
m
k
1
,...,k
m
∈N
k
1
,k
2
,...,k
m
m
k
1
+...+k
m
=n
You’ll be far better off if your remember the reasoning behind the Multinomial Theo-
rem rather than this monstrous equation,
3 Poker Hands
There are 52 cards in a deck,Each card has a suit and a value,There are four suits,
spades
hearts clubs diamonds
And there are 13 values,
jack
queen
king
ace
2,3,4,5,6,7,8,9,
J
,Q,
K
,
A
Thus,for example,8? is the 8 of hearts and A? is the ace of spades,Values farther to the
right in this list are considered,higher” and values to the left are,lower”,
Counting III 5
Five-Card Draw is a card game in which each player is initially dealt a hand,a subset
of 5 cards,(Then the game gets complicated,but let’s not worry about that.) The number
of different hands in Five-Card Draw is the number of 5-element subsets of a 52-element
set,which is 52 choose 5,
52
total # of hands = = 2,598,960
5
Let’s get some counting practice by working out the number of hands with various special
properties,
3.1 Hands with a Four-of-a-Kind
A Four-of-a-Kind is a set of four cards with the same value,How many different hands
contain a Four-of-a-Kind? Here a couple examples,
8?,8?,Q?,8?,8?{ }
{ A?,2?,2?,2?,2? }
As usual,the?rst step is to map this question to a sequence-counting problem,A hand
with a Four-of-a-Kind is completely described by a sequence specifying,
1,The value of the four cards,
2,The value of the extra card,
3,The suit of the extra card,
Thus,there is a bijection between hands with a Four-of-a-Kind and sequences consist-
ing of two distinct values followed by a suit,For example,the three hands above are
associated with the following sequences,
(8,Q,?)? 8?,8?,8?,8?,Q?
(2,A,?)?
{
2?,2?,2?,2?,A?
}
{ }
Now we need only count the sequences,There are 13 ways to choose the?rst value,12
ways to choose the second value,and 4 ways to choose the suit,Thus,by the Generalized
Product Rule,there are 13 · 12 · 4 = 624 hands with a Four-of-a-Kind,This means that
only 1 hand in about 4165 has a Four-of-a-Kind; not surprisingly,this is considered a very
good poker hand!
6 Counting III
3.2 Hands with a Full House
A Full House is a hand with three cards of one value and two cards of another value,Here
are some examples,
2?,2?,2?,J?,J?{
5?,5?,5?,7?,7?
}
{ }
Again,we shift to a problem about sequences,There is a bijection between Full Houses
and sequences specifying,
1,The value of the triple,which can be chosen in 13 ways,
2,The suits of the triple,which can be selected in
4
3
ways,
3,The value of the pair,which can be chosen in 12 ways.
4,The suits of the pair,which can be selected in
4
2
ways,
The example hands correspond to sequences as shown below,
(2,{?,?,?},J,{?,?})? 2?,2?,2?,J?,J?{
5?,5?,5?,7?,7?
}
(5,{?,?,?},7,{?,?})? { }
By the Generalized Product Rule,the number of Full Houses is,
4 4
13 · 12 ·
3
·
2
We’re on a roll— but we’re about to hit a speedbump,
3.3 Hands with Two Pairs
How many hands have Two Pairs; that is,two cards of one value,two cards of another
value,and one card of a third value? Here are examples,
3?,3?,Q?,Q?,A?{ }
9?,9?,5?,{ 5?,K? }
Each hand with Two Pairs is described by a sequence consisting of,
1,The value of the?rst pair,which can be chosen in 13 ways,
2,The suits of the?rst pair,which can be selected
4
2
ways,
3,The value of the second pair,which can be chosen in 12 ways.
4,The suits of the second pair,which can be selected in
4
2
ways.
7 Counting III
5,The value of the extra card,which can be chosen in 11 ways,
6,The suit of the extra card,which can be selected in
4
1
= 4 ways,
Thus,it might appear that the number of hands with Two Pairs is,
4 4
13 · 12 · 11 · 4
2
·
2
·
Wrong answer! The problem is that there is not a bijection from such sequences to hands
with Two Pairs,This is actually a 2-to-1 mapping,For example,here are the pairs of
sequences that map to the hands given above,
(3,{?,?},Q,{?,?},A,?)?
3?,3?,Q?,Q?,A?{ }
(Q,{?,?},3,{?,?},A,?)?
(9,{?,?},5,{?,?},K,?)?
9?,9?,5?,
{ 5?,K? }
(5,{?,?},9,{?,?},K,?)?
The problem is that nothing distinguishes the?rst pair from the second,A pair of 5’s and
a pair of 9’s is the same as a pair of 9’s and a pair of 5’s,We avoided this dif?culty in
counting Full Houses because,for example,a pair of 6’s and a triple of kings is different
from a pair of kings and a triple of 6’s,
We ran into precisely this dif?culty last time,when we went from counting arrange-
ments of different pieces on a chessboard to counting arrangements of two identical rooks,
The solution then was to apply the Division Rule,and we can do the same here,In this
case,the Division rule says there are twice as many sequences and hands,so the number
of hands with Two Pairs is actually,
13 ·
4
2
·
12 ·
4
2
·
11 · 4
2
Another Approach
The preceding example was disturbing! One could easily overlook the fact that the map-
ping was 2-to-1 on an exam,fail the course,and turn to a life of crime,You can make the
world a safer place in two ways,
1,Whenever you use a mapping f, A B to translate one counting problem to
another,check the number elements in
→
A that are mapped to each element in B,
This determines the size of A relative to B,You can then apply the Division Rule
with the appropriate correction factor,
?
8 Counting III
2,As an extra check,try solving the same problem in a different way. Multiple ap-
proaches are often available— and all had better give the same answer! (Sometimes
different approaches give answers that look different,but turn out to be the same
after some algebra.)
We already used the?rst method; let’s try the second,There is a bijection between
hands with two pairs and sequences that specify,
13
1,The values of the two pairs,which can be chosen in ways.
2
2,The suits of the lower-value pair,which can be selected in
4
2
ways,
3,The suits of the higher-value pair,which can be selected in
4
2
ways,
4,The value of the extra card,which can be chosen in 11 ways,
5,The suit of the extra card,which can be selected in
4
1
= 4 ways,
For example,the following sequences and hands correspond,
({3,Q},{?,?},{?,?},A,?)?
({9,5},{?,?},{?,?},K,?)?
{
{
3?,
9?,
3?,
9?,
Q?,
5?,
Q?,
5?,
A?
K?
}
}
Thus,the number of hands with two pairs is,
13 4 4
2
·
2
·
2
· 11 · 4
This is the same answer we got before,though in a slightly different form,
3.4 Hands with Every Suit
How many hands contain at least one card from every suit? Here is an example of such a
hand,
7?,K?,3?,A?,2?{ }
Each such hand is described by a sequence that speci?es,
1,The values of the diamond,the club,the heart,and the spade,which can be selected
in 13 · 13 · 13 · 13 = 13
4
ways,
2,The suit of the extra card,which can be selected in 4 ways,
3,The value of the extra card,which can be selected in 12 ways,
9 Counting III
For example,the hand above is described by the sequence,
(7,K,A,2,?,3) 7?,K?,A?,2?,3 { }
Are there other sequences that correspond to the same hand? There is one more! We
could equally well regard either the 3? or the 7? as the extra card,so this is actually a
2-to-1 mapping,Here are the two sequences corresponding to the example hand,
(7,K,A,2,?,3)
7?,K?,A?,2?,3?{ }
(3,K,A,2,?,7)
Therefore,the number of hands with every suit is,
13
4
4 12· ·
2
4 Magic Trick
There is a Magician and an Assistant,The Assistant goes into the audience with a deck
of 52 cards while the Magician looks away,Five audience members each select one card
from the deck,The Assistant then gathers up the?ve cards and reveals four of them to
the Magician,one at a time,The Magician concentrates for a short time and then correctly
names the secret,?fth card!
4.1 The Secret
The Assistant somehow communicated the secret card to the Magician just by naming the
other four cards,In particular,the Assistant has two ways to communicate,
1,He can announce the four cards in any order,The number of orderings of four cards
is 4! = 24,so this alone is insuf?cient to identify which of the remaining 48 cards is
the secret one,
2,The Assistant can also choose which four of the?ve cards to reveal in binom54 =
5 different ways,Of course,the Magician can not determine which of these?ve
possibilities the Assistant selected,since he does not know the secret card,
Nevertheless,these two forms of communication allow the Assistant to covertly reveal
the secret card to the Magician,
Our counting tools give a lot of insight into the magic trick,Put all the sets of 5 cards
in a collection X on the left,And put all the sequences of 4 distinct cards in a collection Y
on the right,
10 Counting III
Y = all
X =
all sets of
5 cards
sequences of 4
distinct cards
{8?,K?,Q?,2?,6?}
{8?,K?,Q?,9?,6?}
h
h
h
h
h
h
h
h
h
h
h
hh
P
P
P
P
P
P
(
(
(
(
(
(
(
(
(
(
(
((
(8?,K?,Q?,2?)
(K?,8?,Q?,2?)
(K?,8?,6?,Q?)
For example,{8?,K?,Q?,2?,6?} is an element of X on the left,If the audience selects
this set of 5 cards,then there are many different 4-card sequences on the right in set Y
that the Assistant could choose to reveal,including (8?,K?,Q?,2?),(K?,8?,Q?,2?),
and (K?,8?,6?,Q?),
Let’s think about this problem in terms of graphs,Regard the elements of X and Y as
the vertices of a bipartite graph,Put an edge between a set of 5 cards and a sequence of
4 if every card in the sequence is also in the set,In other words,if the audience selects
a set of cards,then the Assistant must reveal a sequence of cards that is adjacent in the
bipartite graph,Some edges are shown in the diagram above,
What we need to perform the trick is a matching for the X vertices; that is,we need
a subset of edges that join every vertex on the left to exactly one,distinct vertex on the
right,If such a matching exists,then the Assistant and Magician can agree one in advance,
Then,when the audience selects a set of 5 cards,the Assistant reveals the corresponding
sequence of 4 cards,The Magician translates back to the correspoding set of 5 cards and
names the one not already revealed,
For example,suppose the Assistant and Magician agree on a matching containing the
two bold edges in the diagram above,If the audience selects the set {8?,K?,Q?,9?,6?},
then the Assistant reveals the corresponding sequence (K?,8?,6?,Q?),The Magician
names the one card in the corresponding set not already revealed,the 9?,Notice that the
sets must be matched with distinct sequences; if the Assistant revealed the same sequence
when the audience picked the set {8?,K?,Q?,2?,6?},then the Magician would be
unable to determine whether the remaining card was the 9? or 2?!
The only remaining question is whether a matching for the X vertices exists,This is
precisely the subject of Hall’s Theorem,Regard the X vertices as girls,the Y vertices as
boys,and each edge as an indication that a girl likes a boy,Then a matching for the girls
exists if and only if the marriage condition is satis?ed,
Every subset of girls likes at least as large a set of boys,
Let’s prove that the marriage condition holds for the magic trick graph,We’ll need a
couple preliminary facts,
?
Counting III 11
Each vertex on the left has degree 5 4! = 120,since there are?ve ways to select the ·
card kept secret and there are 4! permutations of the remaining 4 cards,In terms of
the marriage metaphor,every girl like 120 boys,
Each vertex on the right has degree 48,since there are 48 possibilities for the?fth
card,Thus,every boy is liked by 48 girls,
Now let S be an arbitrary set of vertices on the left,which we’re regarding as girls,There
are 120|S| edges incident to vertices in this set,Since each boy is liked by at most 48 girls,
this set of girls likes at least 120 S /48 ≥ S different boys,Thus,the marriage condition | | | |
is satis?ed,a matching exists by Hall’s Theorem,and the trick can be done without magic!
4.2 The Real Secret
You might not?nd the preceding answer very satisfying,After all,as a practical matter,
the Assistant and the Magician can not memorize a matching containing
52
= 2,598,960
5
edges! The remaining challenge is to choose a matching that can be readily computed on
the?y,We’ll describe one approach,As an running example,suppose that the audience
selects,
10? 9? 3? Q? J?
The Assistant picks out two cards of the same suit,In the example,the assistant
might choose the 3? and 10?,
The Assistant locates the values of these two cards on the cycle shown below,
A
K 2
Q
3
J 4
10 5
9 6
8 7
For any two distinct values on this cycle,one is always between 1 and 6 hops clock-
wise from the other,For example,the 3? is 6 hops clockwise from the 10?,
The more counterclockwise of these two cards is revealed?rst,and the other be-
comes the secret card,Thus,in our example,the 10? would be revealed,and the 3?
would be the secret card,Therefore,
– The suit of the secret card is the same as the suit of the?rst card revealed,
12 Counting III
– The value of the secret card is between 1 and 6 hops clockwise from the value
of the?rst card revealed,
All that remains is to communicate a number between 1 and 6,The Magician and
Assistant agree beforehand on an ordering of all the cards in the deck from smallest
to largest such as,
A? 2?,.,K? A? 2?,.,Q? A? 2?,.,Q? A? 2?,.,Q?
The order in which the last three cards are revealed communicates the number ac-
cording to the following scheme,
( small,medium,large ) = 1
( small,large,medium ) = 2
( medium,small,large ) = 3
( medium,large,small ) = 4
( large,small,medium ) = 5
( large,medium,small ) = 6
In the example,the Assistant wants to send 6 and so reveals the remaining three
cards in large,medium,small order,Here is the complete sequence that the Magi-
cian sees,
10? Q? J? 9?
The Magician starts with the?rst card,10?,and hops 6 values clockwise to reach
3?,which is the secret card!
4.3 Same Trick with Four Cards?
Suppose that the audience selects only four cards and the Assistant reviews a sequence of
three to the Magician,Can the Magician determine the fourth card?
Let X be all the sets of four cards that the audience might select,and let Y be all the
sequences of three cards that the Assistant might reveal,Now,one on hand,we have
52
X| = = 270,725 |
4
by the Subset Rule,On the other hand,we have
Y = 52 · 51 · 50 = 132,600 | |
by the Generalized Product Rule,Thus,by the Pigeonhole Principle,the Assistant must
reveal the same sequence of three cards for some two different sets of four,This is bad news
for the Magician,if he hears that sequence of three,then there are at least two possibilities
for the fourth card which he cannot distinguish!
Counting III 13
5 Combinatorial Proof
Suppose you have n different T-shirts only want to keep k,You could equally well select
the k shirts you want to keep or select the complementary set of n? k shirts you want to
throw out,Thus,the number of ways to select k shirts from among n must be equal to the
number of ways to select n? k shirts from among n,Therefore,
n n
=
k n? k
This is easy to prove algebraically,since both sides are equal to,
n!
k! (n? k)!
But we didn’t really have to resort to algebra; we just used counting principles,
Hmm,
5.1 Boxing
Ishan,famed 6.042 TA,has decided to try out for the US Olympic boxing team,After all,
he’s watched all of the Rocky movies and spent hours in front of a mirror sneering,“Yo,
you wanna piece a’ me?!” Ishan?gures that n people (including himself) are competing
for spots on the team and only k will be selected,As part of maneuvering for a spot on the
team,he need to work out how many different teams are possible,There are two cases to
consider,
Ishan is selected for the team,and his k? 1 teammates are selected from among the
other n? 1 competitors,The number of different teams that be formed in this way
is,
n? 1
k? 1
Ishan is not selected for the team,and all k team members are selected from among
the other n? 1 competitors,The number of teams that can be formed this way is,
n? 1
k
All teams of the?rst type contain Ishan,and no team of the second type does; therefore,
the two sets of teams are disjoint,Thus,by the Sum Rule,the total number of possible
Olympic boxing teams is,
n? 1 n? 1
+
kk? 1
14 Counting III
Christos,equally-famed 6.042 TA,thinks Ishan isn’t so tough and so he might as well
try out also,He reasons that n people (including himself) are trying out for k spots,Thus,
the number of ways to select the team is simply,
n
k
Christos and Ishan each correctly counted the number of possible boxing teams; thus,
their answers must be equal,So we know,
nn? 1 n? 1
+ =
k kk? 1
This is called Pascal’s Identity,And we proved it without any algebra! Instead,we relied
purely on counting techniques,
5.2 Combinatorial Proof
A combinatorial proof is an argument that establishes an algebraic fact by relying on
counting principles,Many such proofs follow the same basic outline,
1,De?ne a set S,
2,Show that |S| = n by counting one way,
3,Show that |S| = m by counting another way,
4,Conclude that n = m,
In the preceding example,S was the set of all possible Olympic boxing teams,Ishan
n
computed |S| =
n?1
+
n?1
by counting one way,and Christos computed |S| = by
k kk?1
counting another,Equating these two expressions gave Pascal’s Identity,
More typically,the set S is de?ned in terms of simple sequences or sets rather than an
elaborate story,Here is less-colorful example of a combinatorial argument,
Theorem 3,
n
n 2n 3n
=
r n? r n
r=0
Proof,We give a combinatorial proof,Let S be all n-card hands that can be dealt from a
deck containing n red cards (numbered 1,...,n) and 2n black cards (numbered 1,...,2n),
First,note that every 3n-element set has
3n
S =| |
n
15 Counting III
n-element subsets,
From another perspective,the number of hands with exactly r red cards is
n 2n
r n? r
n 2n
since there are ways to choose the r red cards and
n?r
ways to choose the n? r black
r
cards,Since the number of red cards can be anywhere from 0 to n,the total number of
n-card hands is,
n
n 2n
S =
r n? r
| |
r=0
Equating these two expressions for |S| proves the theorem,
Combinatorial proofs are almost magical,Theorem 3 looks pretty scary,but we proved
it without any algebraic manipulations at all,The key to constructing a combinatorial
proof is choosing the set S properly,which can be tricky,Generally,the simpler side of
the equation should provide some guidance,For example,the right side of Theorem 3 is
3n
,which suggests choosing S to be all n-element subsets of some 3n-element set,
n
