6.042/18.062J Mathematics for Computer Science March 31,2005
Srini Devadas and Eric Lehman Lecture Notes
Counting II
We realize everyone has been working pretty hard this term
1
,and we’re considering
awarding some prizes for truly exceptional coursework,Here are some possible categories,
Best Administrative Critique We asserted that the quiz was closed-book,On the cover
page,one strong candidate for this award wrote,“There is no book.”
Best Collaboration Statement Inspired by the student who wrote,I worked alone” on
quiz 1,
Olfactory Fixation Award A surprisingly competitive category this term,this goes to the
student who comes up with the greatest number of odor-related mathematical ex-
amples,
We also considered some less?attering categories such as Proof Most Likely Readable
from the Surface of the Moon,Solution Most Closely Resembling a Football Play Diagram
with Good Yardage Potential,etc,But then we realized that you all might think up sim-
ilar,awards” for the course staff and decided to turn the whole matter into a counting
problem,In how many ways can,say,three different prizes be awarded to n people?
Remember our basic strategy for counting,
1,Learn to count sequences,
2,Translate everything else into a sequence-counting problem via bijections,
We’ll?esh out this strategy considerably today,but the rough outline above is good
enough for now,
So we?rst need to?nd a bijection that translates the problem about awards into a
problem about sequences,Let P be the set of n people in 6.042,Then there is a bijection
from ways of awarding the three prizes to the set P× P× P,In particular,the assignment,
“person x wins prize #1,y wins prize #2,and z wins prize #3”
maps to the sequence (x,y,z),All that remains is to count these sequences,By the Product
Rule,we have,
= P P PP × P × P| | |
3
|·| |·| |
= n
Thus,there are n
3
ways to award the prizes to a class of n people.
1
Actually,these notes were written last fall,but the problem sets are no easier this term.,-)
2 Counting II
1 The Generalized Product Rule
What if the three prizes must be awarded to different students? As before,we could map
the assignment
“person x wins prize #1,y wins prize #2,and z wins prize #3”
to the triple (x,y,z) ∈ P × P × P,But this function is no longer a bijection,For example,
no valid assignment maps to the triple (Dave,Dave,Becky) because Dave is not allowed
to receive two awards,However,there is a bijection from prize assignments to the set,
S = {(x,y,z) ∈ P ×P ×P x,y,and z are different people}|
This reduces the original problem to a problem of counting sequences,Unfortunately,the
Product Rule is of no help in counting sequences of this type because the entries depend
on one another; in particular,they must all be different,However,a slightly sharper tool
does the trick,
Rule 1 (Generalized Product Rule),Let S be a set of length-k sequences,If there are,
n
1
possible?rst entries,
n
2
possible second entries for each?rst entry,
n
3
possible third entries for each combination of?rst and second entries,etc,
then,
S = n
1
n
k
| | ·n
2
·n
3
···
In the awards example,S consists of sequences (x,y,z),There are n ways to choose x,
the recipient of prize #1,For each of these,there are n?1 ways to choose y,the recipient
of prize #2,since everyone except for person x is eligible,For each combination of x and
y,there are n?2 ways to choose z,the recipient of prize #3,because everyone except for
x and y is eligible,Thus,according to the Generalized Product Rule,there are
S = n ·(n?1) ·(n?2)| |
ways to award the 3 prizes to different people,
1.1 Defective Dollars
A dollar is defective some digit appears more than once in the 8-digit serial number,If you
check your wallet,you’ll be sad to discover that defective dollars are all-too-common,
Counting II 3
In fact,how common are nondefective dollars? Assuming that the digit portions of serial
numbers all occur equally often,we could answer this question by computing,
# of serial #’s with all digits different
fraction dollars that are nondefective =
total # of serial #’s
Let’s?rst consider the denominator,Here there are no restrictions; there are are 10 possi-
ble?rst digits,10 possible second digits,10 third digits,and so on,Thus,the total number
of 8-digit serial numbers is 10
8
by the Generalized Product Rule,(Alternatively,you could
conclude this using the ordinary Product Rule; however,the Generalized Product Rule is
strictly more powerful,So you might as well forget the orignial Product Rule now and
free up some brain space for 6.002.)
Next,let’s turn to the numerator,Now we’re not permitted to use any digit twice,So
there are still 10 possible?rst digits,but only 9 possible second digits,8 possible third
digits,and so forth,Thus there are
10!
10 · 9 8 7 6 5 4 3 = · · · · · ·
2
= 1,814,400
serial numbers with all digits different,Plugging these results into the equation above,
we?nd,
1,814,400
fraction dollars that are nondefective =
100,000,000
= 1.8144%
1.2 A Chess Problem
In how many different ways can we place a pawn (p),a knight (k),and a bishop (b) on
a chessboard so that no two pieces share a row or a column? A valid con?guration is
shown below on the the left,and an invalid con?guration is shown on the right,
k
b
p
p
b k
valid invalid
4 Counting II
First,we map this problem about chess pieces to a question about sequences,There is a
bijection from con?gurations to sequences
(r
p
,c
p
,r
k
,c
k
,r
b
,c
b
)
where r
p
,r
k
,and r
b
are distinct rows and c
p
,c
k
,and c
b
are distinct columns,In particular,
r
p
is the pawn’s row,c
p
is the pawn’s column,r
k
is the knight’s row,etc,Now we can
count the number of such sequences using the Generalized Product Rule,
r
p
is one of 8 rows
c
p
is one of 8 columns?
r
k
is one of 7 rows (any one but r
p
)
c
k
is one of 7 columns (any one but c
p
)
r
b
is one of 6 rows (any one but r
p
or r
k
)
c
b
is one of 6 columns (any one but c
p
or c
k
)
Thus,the total number of con?gurations is (8 7 ·6)
2
.·
1.3 Permutations
A permutation of a set S is a sequence that contains every element of S exactly once,For
example,here are all the permutations of the set {a,b,c},
(a,b,c) (a,c,b) (b,a,c)
(b,c,a) (c,a,b) (c,b,a)
How many permutations of an n-element set are there? Well,there are nchoices for the
rst element,For each of these,there are n?1 remaining choices for the second element,
For every combination of the?rst two elements,there are n?2 ways to choose the third
element,and so forth,Thus,there are a total of
n·(n?1) ·(n?2) 3 2 1 = n!··· · ·
permutations of an n-element set,In particular,this formula says that there are 3! = 6
permuations of the 3-element set {a,b,c},which is the number we found above,
Permutations will come up again in this course approximately 1.6 bazillion times,In
fact,permutations are the reason why factorial comes up so often and why we taught you
Stirling’s approximation,
n
n
n! ～
√
2πn
e
Counting II 5
2 The Division Rule
We can count the number of people in a room by counting ears and dividing by two,Or
we could count the number of?ngers and divide by 10,Or we could count the number
of?ngers and toes and divide by 20,(Someone is probably short a?nger or has an extra
ear,but let’s not worry about that right now.) These observations lead to an important
counting rule,
A k-to-1 function maps exactly k elements of the domain to every element of the range,
For example,the function mapping each ear to its owner is 2-to-1,
-
ear 1 person A
3
ear 2
P
P
P
P
P
P
ear 3
q
person B
ear 4
q
person C
P
P
P
P
P
P
ear 5
-
ear 6
Similarly,the function mapping each?nger to its owner is 10-to-1,And the function
maping each each?nger or toe to its owner is 20-to-1,Now just as a bijection implies two
sets are the same size,a k-to-1 function implies that the domain is k times larger than the
domain,
Rule 2 (Division Rule),If f, A → B is k-to-1,then |A = k B|.| ·|
Suppose A is the set of ears in the room and B is the set of people,Since we know
there is a 2-to-1 mapping from ears to people,the Division Rule says that |A = 2 B| or,| ·|
equivalently,|B = A /2,Thus,the number of people is half the number of ears,| | |
Now this might seem like a stupid way to count people,But,surprisingly,many count-
ing problems are made much easier by initially counting every item multiple times and
then correcting the answer using the Division Rule,Let’s look at some examples,
2.1 Another Chess Problem
In how many different ways can you place two identical rooks on a chessboard so that
they do not share a row or column? A valid con?guration is shown below on the left,and
6 Counting II
an invalid con?guration is shown on the right,
r
r
r
r
valid invalid
Let A be the set of all sequences
(r
1
,c
1
,r
2
,c
2
)
where r
1
and r
2
are distinct rows and c
1
and c
2
are distinct columns,Let B be the set of all
valid rook con?gurations,There is a natural function f from set A to set B; in particular,
f maps the sequence (r
1
,c
1
,r
2
,c
2
) to a con?guration with one rook in row r
1
,column c
1
and the other rook in row r
2
,column c
2
,
But now there’s a snag,Consider the sequences,
(1,1,8,8) and (8,8,1,1)
The?rst sequence maps to a con?guration with a rook in the lower-left corner and a rook
in the upper-right corner,The second sequence maps to a con?guration with a rook in the
upper-right corner and a rook in the lower-left corner,The problem is that those are two
different ways of describing the same con?guration! In fact,this arrangement is shown on
the left side in the diagram above,
More generally,the function f map exactly two sequences to every board con?guration;
that is f is a 2-to-1 function,Thus,by the quotient rule,|A = 2 ·|B, Rearranging terms | |
gives,
|B =
|A|
|
2
(8 · 7)
2
=
2
On the second line,we’ve computed the size of A using the General Product Rule just as
in the earlier chess problem,
2.2 Knights of the Round Table
In how many ways can King Arthur seat n different knights at his round table? Two
seatings are considered equivalent if one can be obtained from the other by rotation,For
example,the following two arrangements are equivalent,
Counting II 7
a34a33
a35a32k1
k2
k3
k4
a34a33
a35a32k3
k4
k1
k2
Let A be all the permutations of the knights,and let B be the set of all possible seating
arrangements at the round table,We can map each permutaton in set A to a circular
seating arrangement in set B by seating the first knight in the permutation anywhere,
putting the second knight to his left,the third knight to the left of the second,and so forth
all the way around the table,For example:
(k2,k4,k1,k3)?
a34a33
a35a32k2
k4
k1
k3
This mapping is actually an n-to-1 function from A to B,since all n cyclic shifts of the
original sequence map to the same seating arrangement,In the example,n = 4 different
sequences map to the same seating arranement:
(k2,k4,k1,k3)
(k4,k1,k3,k2)
(k1,k3,k2,k4)
(k3,k2,k4,k1)
a34a33
a35a32k2
k4
k1
k3
Therefore,by the division rule,the number of circular seating arrangements is:
|B| = |A|n
= n!n
= (n?1)!
Note that |A| = n! since there are n! permutations of n knights.
3 Inclusion-Exclusion
How big is a union of sets? For example,suppose there are 60 Math majors,200 EECS
majors,and 40 Physics majors,How many students are there in these three departments?
8 Counting II
Let M be the set of Math majors,E be the set of EECS majors,and P be the set of Physics
majors,In these terms,we’re asking for M ∪ E ∪ P,| |
The Sum Rule says that the size of union of disjoint sets is the sum of their sizes,
M ∪ E ∪ P = M| + E + P (if M,E,and P are disjoint) | | | | | | |
However,the sets M,E,and P might not be disjoint,For example,there might be a
student majoring in both Math and Physics,Such a student would be counted twice on
the right sides of this equation,once as an element of M and once as an element of P,
Worse,there might be a triple-major counting three times on the right side!
Our last counting rule determines the size of a union of sets that are not necessarily
disjoint,Before we state the rule,let’s build some intuition by considering some easier
special cases,unions of just two or three sets,
3.1 Union of Two Sets
For two sets,S
1
and S
2
,the size of the union is given by the following equation,
S
1
∪ S
2
= S
1
| + S
2
S
1
∩ S
2
(1)| | | | |?| |
Intuitively,each element of S
1
is accounted for in the?rst term,and each element of S
2
is
accounted for in the second term,Elements in both S
1
and S
2
are counted twice— once in
the?rst term and once in the second,This double-counting is corrected by the?nal term,
We can prove equation (1) rigorously by applying the Sum Rule to some disjoint sub-
sets of S
1
∪ S
2
,As a?rst step,we observe that given any two sets,S,T,we can decompose
S into the disjoint sets consisting of those elements in S but not T,and those elements in
S and also in T,That is,S is the union of the disjoint sets S? T and S ∩ T,So by the Sum
Rule we have
|S| = |S? T| +|S ∩ T|,
|S? T| = |S|? |S ∩ T|,
and so
(2)
Now we decompose S
1
∪ S
2
into three disjoint sets,
S
1
∪ S
2
= (S
1
S
2
)∪ (S
2
S
1
)∪ (S
1
∩ S
2
),(3)
Now we have
S
1
∪ S
2
= (S
1
S
2
)∪ (S
2
S
1
)∪ (S
1
∩ S
2
) (by (3))| | | |
= S
1
S
2
+ S
2
S
1
+ S
1
∩ S
2
(Sum Rule) | | | | | |
= (|S
1
S
1
∩ S
2
) + ( S
2
S
1
∩ S
2
) + S
1
∩ S
2
(by (2))|?| | | |?| | | |
= S
1
| + S
2
S
1
∩ S
2
(algebra)| | |?| |
Counting II 9
3.2 Union of Three Sets
So how many students are there in the Math,EECS,and Physics departments? In other
words,what is M ∪ E ∪ P if:| |
M| = 60
|
E| = 200 |
P = 40 | |
The size of a union of three sets is given by a more complicated formula,
S
1
∪ S
2
∪ S
3
= S
1
| + S
2
+ S
3
| | | | | | |
S
1
∩ S
2
S
1
∩ S
3
S
2
∩ S
3
| |?| |?| |
+ S
1
∩ S
2
∩ S
3
| |
Remarkably,the expression on the right accounts for each element in the the union of S
1
,
S
2
,and S
3
exactly once,For example,suppose that x is an element of all three sets,Then x
is counted three times (by the |S
1
,S
2
,and S
3
terms),subtracted off three times (by the | | | | |
S
1
∩ S
2
,S
1
∩ S
3
,and S
2
∩ S
3
terms),and then counted once more (by the S
1
∩ S
2
∩ S
3
| | | | | | | |
term),The net effect is that x is counted just once,
So we can’t answer the original question without knowing the sizes of the various
intersections,Let’s suppose that there are,
4 Math - EECS double majors
3 Math - Physics double majors
11 EECS - Physics double majors
2 triple majors
Then M ∩ E = 4 + 2,M ∩ P = 3 + 2,E ∩ P = 11 + 2,and M ∩ E ∩ P = 2,Plugging | | | | | | | |
all this into the formula gives,
M ∪ E ∪ P = M| + E + P M ∩ E M ∩ P E ∩ P + M ∩ E ∩ P| | | | | | |?| |?| |?| | | |
= 60 + 200 + 40? 6? 5? 13 + 2
= 278
Sequences with 42,04,or 60
In how many permutations of the set {0,1,2,...,9} do either 4 and 2,0 and 4,or 6 and 0
appear consecutively? For example,none of these pairs appears in,
(7,2,9,5,4,1,3,8,0,6)
The 06 at the end doesn’t count; we need 60,On the other hand,both 04 and 60 appear
consecutively in this permutation,
(7,2,5,6,0,4,3,8,1,9)
10 Counting II
Let P
42
be the set of all permutations in which 42 appears; de?ne P
60
and P
04
similarly,
Thus,for example,the permutation above is contained in both P
60
and P
04
,In these terms,
we’re looking for the size of the set P
42
∪P
04
∪P
60
,
First,we must determine the sizes of the individual sets,such as P
60
,We can use a trick,
group the 6 and 0 together as a single symbol,Then there is a natural bijection between
permutations of {0,1,2,...9} containing 6 and 0 consecutively and permutations of,
{60,1,2,3,4,5,7,8,9}
For example,the following two sequences correspond,
(7,2,5,6,0,4,3,8,1,9)? (7,2,5,60,4,3,8,1,9)
There are 9! permutations of the set containing 60,so |P
60
| = 9! by the Bijection Rule,
Similarly,|P
04
| = = 9! as well,|P
42
|
Next,we must determine the sizes of the two-way intersections,such as P
42
∩ P
60
,
Using the grouping trick again,there is a bijection with permutations of the set,
{42,60,1,3,5,7,8,9}
Thus,P
42
∩P
60
= 8!,Similarly,P
60
∩P
04
= 8! by a bijection with the set,| | | |
{604,1,2,3,5,7,8,9}
And P
42
∩P
04
= 8! as well by a similar argument,Finally,note that P
60
∩P
04
∩P
42
= 7!| | | |
by a bijection with the set,
{6042,1,3,5,7,8,9}
Plugging all this into the formula gives,
P
42
∪P
04
∪P
60
= 9! + 9! + 9!?8!?8!?8! + 7! | |
3.3 Union of n Sets
The size of a union of n sets is given by the following rule,
Rule 3 (Inclusion-Exclusion),
n
=|S
1
∪S
2
∪···∪S |
the sum of the sizes of the individual sets
minus the sizes of all two-way intersections
plus the sizes of all three-way intersections
minus the sizes of all four-way intersections
plus the sizes of all?ve-way intersections,etc,
There are various ways to write the Inclusion-Exclusion formula in mathematical sym-
bols,but none are particularly clear,so we’ve just used words,The formulas for unions
of two and three sets are special cases of this general rule,
Counting II 11
4 The Grand Scheme for Counting
The rules and techniques we’ve covered to this point snap together into an overall scheme
for solving elementary counting problems,Here it is,
Grand Scheme for Counting
1,Learn to count sequences using two techniques,
the General Product Rule
the BOOKKEEPER formula
2,Translate everything else to a sequence-counting problem via,
bijections
k-to-1 functions
3,But for unions of sets,use Inclusion-Exclusion,
Everything here should be familiar to you by now,except for the BOOKKEEPER for-
mula,which you’ll see in recitation tomorrow,
Srini Devadas and Eric Lehman Lecture Notes
Counting II
We realize everyone has been working pretty hard this term
1
,and we’re considering
awarding some prizes for truly exceptional coursework,Here are some possible categories,
Best Administrative Critique We asserted that the quiz was closed-book,On the cover
page,one strong candidate for this award wrote,“There is no book.”
Best Collaboration Statement Inspired by the student who wrote,I worked alone” on
quiz 1,
Olfactory Fixation Award A surprisingly competitive category this term,this goes to the
student who comes up with the greatest number of odor-related mathematical ex-
amples,
We also considered some less?attering categories such as Proof Most Likely Readable
from the Surface of the Moon,Solution Most Closely Resembling a Football Play Diagram
with Good Yardage Potential,etc,But then we realized that you all might think up sim-
ilar,awards” for the course staff and decided to turn the whole matter into a counting
problem,In how many ways can,say,three different prizes be awarded to n people?
Remember our basic strategy for counting,
1,Learn to count sequences,
2,Translate everything else into a sequence-counting problem via bijections,
We’ll?esh out this strategy considerably today,but the rough outline above is good
enough for now,
So we?rst need to?nd a bijection that translates the problem about awards into a
problem about sequences,Let P be the set of n people in 6.042,Then there is a bijection
from ways of awarding the three prizes to the set P× P× P,In particular,the assignment,
“person x wins prize #1,y wins prize #2,and z wins prize #3”
maps to the sequence (x,y,z),All that remains is to count these sequences,By the Product
Rule,we have,
= P P PP × P × P| | |
3
|·| |·| |
= n
Thus,there are n
3
ways to award the prizes to a class of n people.
1
Actually,these notes were written last fall,but the problem sets are no easier this term.,-)
2 Counting II
1 The Generalized Product Rule
What if the three prizes must be awarded to different students? As before,we could map
the assignment
“person x wins prize #1,y wins prize #2,and z wins prize #3”
to the triple (x,y,z) ∈ P × P × P,But this function is no longer a bijection,For example,
no valid assignment maps to the triple (Dave,Dave,Becky) because Dave is not allowed
to receive two awards,However,there is a bijection from prize assignments to the set,
S = {(x,y,z) ∈ P ×P ×P x,y,and z are different people}|
This reduces the original problem to a problem of counting sequences,Unfortunately,the
Product Rule is of no help in counting sequences of this type because the entries depend
on one another; in particular,they must all be different,However,a slightly sharper tool
does the trick,
Rule 1 (Generalized Product Rule),Let S be a set of length-k sequences,If there are,
n
1
possible?rst entries,
n
2
possible second entries for each?rst entry,
n
3
possible third entries for each combination of?rst and second entries,etc,
then,
S = n
1
n
k
| | ·n
2
·n
3
···
In the awards example,S consists of sequences (x,y,z),There are n ways to choose x,
the recipient of prize #1,For each of these,there are n?1 ways to choose y,the recipient
of prize #2,since everyone except for person x is eligible,For each combination of x and
y,there are n?2 ways to choose z,the recipient of prize #3,because everyone except for
x and y is eligible,Thus,according to the Generalized Product Rule,there are
S = n ·(n?1) ·(n?2)| |
ways to award the 3 prizes to different people,
1.1 Defective Dollars
A dollar is defective some digit appears more than once in the 8-digit serial number,If you
check your wallet,you’ll be sad to discover that defective dollars are all-too-common,
Counting II 3
In fact,how common are nondefective dollars? Assuming that the digit portions of serial
numbers all occur equally often,we could answer this question by computing,
# of serial #’s with all digits different
fraction dollars that are nondefective =
total # of serial #’s
Let’s?rst consider the denominator,Here there are no restrictions; there are are 10 possi-
ble?rst digits,10 possible second digits,10 third digits,and so on,Thus,the total number
of 8-digit serial numbers is 10
8
by the Generalized Product Rule,(Alternatively,you could
conclude this using the ordinary Product Rule; however,the Generalized Product Rule is
strictly more powerful,So you might as well forget the orignial Product Rule now and
free up some brain space for 6.002.)
Next,let’s turn to the numerator,Now we’re not permitted to use any digit twice,So
there are still 10 possible?rst digits,but only 9 possible second digits,8 possible third
digits,and so forth,Thus there are
10!
10 · 9 8 7 6 5 4 3 = · · · · · ·
2
= 1,814,400
serial numbers with all digits different,Plugging these results into the equation above,
we?nd,
1,814,400
fraction dollars that are nondefective =
100,000,000
= 1.8144%
1.2 A Chess Problem
In how many different ways can we place a pawn (p),a knight (k),and a bishop (b) on
a chessboard so that no two pieces share a row or a column? A valid con?guration is
shown below on the the left,and an invalid con?guration is shown on the right,
k
b
p
p
b k
valid invalid
4 Counting II
First,we map this problem about chess pieces to a question about sequences,There is a
bijection from con?gurations to sequences
(r
p
,c
p
,r
k
,c
k
,r
b
,c
b
)
where r
p
,r
k
,and r
b
are distinct rows and c
p
,c
k
,and c
b
are distinct columns,In particular,
r
p
is the pawn’s row,c
p
is the pawn’s column,r
k
is the knight’s row,etc,Now we can
count the number of such sequences using the Generalized Product Rule,
r
p
is one of 8 rows
c
p
is one of 8 columns?
r
k
is one of 7 rows (any one but r
p
)
c
k
is one of 7 columns (any one but c
p
)
r
b
is one of 6 rows (any one but r
p
or r
k
)
c
b
is one of 6 columns (any one but c
p
or c
k
)
Thus,the total number of con?gurations is (8 7 ·6)
2
.·
1.3 Permutations
A permutation of a set S is a sequence that contains every element of S exactly once,For
example,here are all the permutations of the set {a,b,c},
(a,b,c) (a,c,b) (b,a,c)
(b,c,a) (c,a,b) (c,b,a)
How many permutations of an n-element set are there? Well,there are nchoices for the
rst element,For each of these,there are n?1 remaining choices for the second element,
For every combination of the?rst two elements,there are n?2 ways to choose the third
element,and so forth,Thus,there are a total of
n·(n?1) ·(n?2) 3 2 1 = n!··· · ·
permutations of an n-element set,In particular,this formula says that there are 3! = 6
permuations of the 3-element set {a,b,c},which is the number we found above,
Permutations will come up again in this course approximately 1.6 bazillion times,In
fact,permutations are the reason why factorial comes up so often and why we taught you
Stirling’s approximation,
n
n
n! ～
√
2πn
e
Counting II 5
2 The Division Rule
We can count the number of people in a room by counting ears and dividing by two,Or
we could count the number of?ngers and divide by 10,Or we could count the number
of?ngers and toes and divide by 20,(Someone is probably short a?nger or has an extra
ear,but let’s not worry about that right now.) These observations lead to an important
counting rule,
A k-to-1 function maps exactly k elements of the domain to every element of the range,
For example,the function mapping each ear to its owner is 2-to-1,
-
ear 1 person A
3
ear 2
P
P
P
P
P
P
ear 3
q
person B
ear 4
q
person C
P
P
P
P
P
P
ear 5
-
ear 6
Similarly,the function mapping each?nger to its owner is 10-to-1,And the function
maping each each?nger or toe to its owner is 20-to-1,Now just as a bijection implies two
sets are the same size,a k-to-1 function implies that the domain is k times larger than the
domain,
Rule 2 (Division Rule),If f, A → B is k-to-1,then |A = k B|.| ·|
Suppose A is the set of ears in the room and B is the set of people,Since we know
there is a 2-to-1 mapping from ears to people,the Division Rule says that |A = 2 B| or,| ·|
equivalently,|B = A /2,Thus,the number of people is half the number of ears,| | |
Now this might seem like a stupid way to count people,But,surprisingly,many count-
ing problems are made much easier by initially counting every item multiple times and
then correcting the answer using the Division Rule,Let’s look at some examples,
2.1 Another Chess Problem
In how many different ways can you place two identical rooks on a chessboard so that
they do not share a row or column? A valid con?guration is shown below on the left,and
6 Counting II
an invalid con?guration is shown on the right,
r
r
r
r
valid invalid
Let A be the set of all sequences
(r
1
,c
1
,r
2
,c
2
)
where r
1
and r
2
are distinct rows and c
1
and c
2
are distinct columns,Let B be the set of all
valid rook con?gurations,There is a natural function f from set A to set B; in particular,
f maps the sequence (r
1
,c
1
,r
2
,c
2
) to a con?guration with one rook in row r
1
,column c
1
and the other rook in row r
2
,column c
2
,
But now there’s a snag,Consider the sequences,
(1,1,8,8) and (8,8,1,1)
The?rst sequence maps to a con?guration with a rook in the lower-left corner and a rook
in the upper-right corner,The second sequence maps to a con?guration with a rook in the
upper-right corner and a rook in the lower-left corner,The problem is that those are two
different ways of describing the same con?guration! In fact,this arrangement is shown on
the left side in the diagram above,
More generally,the function f map exactly two sequences to every board con?guration;
that is f is a 2-to-1 function,Thus,by the quotient rule,|A = 2 ·|B, Rearranging terms | |
gives,
|B =
|A|
|
2
(8 · 7)
2
=
2
On the second line,we’ve computed the size of A using the General Product Rule just as
in the earlier chess problem,
2.2 Knights of the Round Table
In how many ways can King Arthur seat n different knights at his round table? Two
seatings are considered equivalent if one can be obtained from the other by rotation,For
example,the following two arrangements are equivalent,
Counting II 7
a34a33
a35a32k1
k2
k3
k4
a34a33
a35a32k3
k4
k1
k2
Let A be all the permutations of the knights,and let B be the set of all possible seating
arrangements at the round table,We can map each permutaton in set A to a circular
seating arrangement in set B by seating the first knight in the permutation anywhere,
putting the second knight to his left,the third knight to the left of the second,and so forth
all the way around the table,For example:
(k2,k4,k1,k3)?
a34a33
a35a32k2
k4
k1
k3
This mapping is actually an n-to-1 function from A to B,since all n cyclic shifts of the
original sequence map to the same seating arrangement,In the example,n = 4 different
sequences map to the same seating arranement:
(k2,k4,k1,k3)
(k4,k1,k3,k2)
(k1,k3,k2,k4)
(k3,k2,k4,k1)
a34a33
a35a32k2
k4
k1
k3
Therefore,by the division rule,the number of circular seating arrangements is:
|B| = |A|n
= n!n
= (n?1)!
Note that |A| = n! since there are n! permutations of n knights.
3 Inclusion-Exclusion
How big is a union of sets? For example,suppose there are 60 Math majors,200 EECS
majors,and 40 Physics majors,How many students are there in these three departments?
8 Counting II
Let M be the set of Math majors,E be the set of EECS majors,and P be the set of Physics
majors,In these terms,we’re asking for M ∪ E ∪ P,| |
The Sum Rule says that the size of union of disjoint sets is the sum of their sizes,
M ∪ E ∪ P = M| + E + P (if M,E,and P are disjoint) | | | | | | |
However,the sets M,E,and P might not be disjoint,For example,there might be a
student majoring in both Math and Physics,Such a student would be counted twice on
the right sides of this equation,once as an element of M and once as an element of P,
Worse,there might be a triple-major counting three times on the right side!
Our last counting rule determines the size of a union of sets that are not necessarily
disjoint,Before we state the rule,let’s build some intuition by considering some easier
special cases,unions of just two or three sets,
3.1 Union of Two Sets
For two sets,S
1
and S
2
,the size of the union is given by the following equation,
S
1
∪ S
2
= S
1
| + S
2
S
1
∩ S
2
(1)| | | | |?| |
Intuitively,each element of S
1
is accounted for in the?rst term,and each element of S
2
is
accounted for in the second term,Elements in both S
1
and S
2
are counted twice— once in
the?rst term and once in the second,This double-counting is corrected by the?nal term,
We can prove equation (1) rigorously by applying the Sum Rule to some disjoint sub-
sets of S
1
∪ S
2
,As a?rst step,we observe that given any two sets,S,T,we can decompose
S into the disjoint sets consisting of those elements in S but not T,and those elements in
S and also in T,That is,S is the union of the disjoint sets S? T and S ∩ T,So by the Sum
Rule we have
|S| = |S? T| +|S ∩ T|,
|S? T| = |S|? |S ∩ T|,
and so
(2)
Now we decompose S
1
∪ S
2
into three disjoint sets,
S
1
∪ S
2
= (S
1
S
2
)∪ (S
2
S
1
)∪ (S
1
∩ S
2
),(3)
Now we have
S
1
∪ S
2
= (S
1
S
2
)∪ (S
2
S
1
)∪ (S
1
∩ S
2
) (by (3))| | | |
= S
1
S
2
+ S
2
S
1
+ S
1
∩ S
2
(Sum Rule) | | | | | |
= (|S
1
S
1
∩ S
2
) + ( S
2
S
1
∩ S
2
) + S
1
∩ S
2
(by (2))|?| | | |?| | | |
= S
1
| + S
2
S
1
∩ S
2
(algebra)| | |?| |
Counting II 9
3.2 Union of Three Sets
So how many students are there in the Math,EECS,and Physics departments? In other
words,what is M ∪ E ∪ P if:| |
M| = 60
|
E| = 200 |
P = 40 | |
The size of a union of three sets is given by a more complicated formula,
S
1
∪ S
2
∪ S
3
= S
1
| + S
2
+ S
3
| | | | | | |
S
1
∩ S
2
S
1
∩ S
3
S
2
∩ S
3
| |?| |?| |
+ S
1
∩ S
2
∩ S
3
| |
Remarkably,the expression on the right accounts for each element in the the union of S
1
,
S
2
,and S
3
exactly once,For example,suppose that x is an element of all three sets,Then x
is counted three times (by the |S
1
,S
2
,and S
3
terms),subtracted off three times (by the | | | | |
S
1
∩ S
2
,S
1
∩ S
3
,and S
2
∩ S
3
terms),and then counted once more (by the S
1
∩ S
2
∩ S
3
| | | | | | | |
term),The net effect is that x is counted just once,
So we can’t answer the original question without knowing the sizes of the various
intersections,Let’s suppose that there are,
4 Math - EECS double majors
3 Math - Physics double majors
11 EECS - Physics double majors
2 triple majors
Then M ∩ E = 4 + 2,M ∩ P = 3 + 2,E ∩ P = 11 + 2,and M ∩ E ∩ P = 2,Plugging | | | | | | | |
all this into the formula gives,
M ∪ E ∪ P = M| + E + P M ∩ E M ∩ P E ∩ P + M ∩ E ∩ P| | | | | | |?| |?| |?| | | |
= 60 + 200 + 40? 6? 5? 13 + 2
= 278
Sequences with 42,04,or 60
In how many permutations of the set {0,1,2,...,9} do either 4 and 2,0 and 4,or 6 and 0
appear consecutively? For example,none of these pairs appears in,
(7,2,9,5,4,1,3,8,0,6)
The 06 at the end doesn’t count; we need 60,On the other hand,both 04 and 60 appear
consecutively in this permutation,
(7,2,5,6,0,4,3,8,1,9)
10 Counting II
Let P
42
be the set of all permutations in which 42 appears; de?ne P
60
and P
04
similarly,
Thus,for example,the permutation above is contained in both P
60
and P
04
,In these terms,
we’re looking for the size of the set P
42
∪P
04
∪P
60
,
First,we must determine the sizes of the individual sets,such as P
60
,We can use a trick,
group the 6 and 0 together as a single symbol,Then there is a natural bijection between
permutations of {0,1,2,...9} containing 6 and 0 consecutively and permutations of,
{60,1,2,3,4,5,7,8,9}
For example,the following two sequences correspond,
(7,2,5,6,0,4,3,8,1,9)? (7,2,5,60,4,3,8,1,9)
There are 9! permutations of the set containing 60,so |P
60
| = 9! by the Bijection Rule,
Similarly,|P
04
| = = 9! as well,|P
42
|
Next,we must determine the sizes of the two-way intersections,such as P
42
∩ P
60
,
Using the grouping trick again,there is a bijection with permutations of the set,
{42,60,1,3,5,7,8,9}
Thus,P
42
∩P
60
= 8!,Similarly,P
60
∩P
04
= 8! by a bijection with the set,| | | |
{604,1,2,3,5,7,8,9}
And P
42
∩P
04
= 8! as well by a similar argument,Finally,note that P
60
∩P
04
∩P
42
= 7!| | | |
by a bijection with the set,
{6042,1,3,5,7,8,9}
Plugging all this into the formula gives,
P
42
∪P
04
∪P
60
= 9! + 9! + 9!?8!?8!?8! + 7! | |
3.3 Union of n Sets
The size of a union of n sets is given by the following rule,
Rule 3 (Inclusion-Exclusion),
n
=|S
1
∪S
2
∪···∪S |
the sum of the sizes of the individual sets
minus the sizes of all two-way intersections
plus the sizes of all three-way intersections
minus the sizes of all four-way intersections
plus the sizes of all?ve-way intersections,etc,
There are various ways to write the Inclusion-Exclusion formula in mathematical sym-
bols,but none are particularly clear,so we’ve just used words,The formulas for unions
of two and three sets are special cases of this general rule,
Counting II 11
4 The Grand Scheme for Counting
The rules and techniques we’ve covered to this point snap together into an overall scheme
for solving elementary counting problems,Here it is,
Grand Scheme for Counting
1,Learn to count sequences using two techniques,
the General Product Rule
the BOOKKEEPER formula
2,Translate everything else to a sequence-counting problem via,
bijections
k-to-1 functions
3,But for unions of sets,use Inclusion-Exclusion,
Everything here should be familiar to you by now,except for the BOOKKEEPER for-
mula,which you’ll see in recitation tomorrow,
