?
6.042/18.062J Mathematics for Computer Science April 1,2005
Srini Devadas and Eric Lehman
Notes for Recitation 14
Counting Rules
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
···
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
Rule 2 (Division Rule),If f, A → B is k-to-1,then |A = k B|.| ·|
2 Recitation 14
The Generalized Product Rule
Problem 1,Solve the following counting problems using the generalized product rule,
(a) Next week,I’m going to get really?t! On day 1,I’ll exercise for 5 minutes,On
each subsequent day,I’ll exercise 0,1,2,or 3 minutes more than the previous day,
For example,the number of minutes that I exercise on the seven days of next week
might be 5,6,9,9,9,11,12,How many such sequences are possible?
Solution,The number of minutes on the?rst day can be selected in 1 way,The
number of minutes on each subsequent day can be selected in 4 ways,Therefore,
the number of exercise sequences is 1·4
6
by the extended product rule,
(b) An r-permutation of a set is a sequence of r distinct elements of that set,For
example,here are all the 2-permutations of {a,b,c,d},
(a,b) (a,c) (a,d)
(b,a) (b,c) (b,d)
(c,a) (c,b) (c,d)
(d,a) (d,b) (d,c)
How many r-permutations of an n-element set are there? Express your answer us-
ing factorial notation,
Solution,There are n ways to choose the?rst element,n? 1 ways to choose the
second,n? 2 ways to choose the third,.,,,and there are n? r + 1 ways to choose
the r-th element,Thus,there are,
n!
n·(n?1)·( n?r + 1) =
(n?r)!
n?2)···(
r-permutations of an n-element set,
(c) How many n × n matrices are there with distinct entries drawn from {1,...,p},
where p ≥ n
2
Solution,There are p ways to choose the?rst entry,p?1 ways to choose the second
for each way of choosing the?rst,p? 2 ways of choosing the third,and so forth,In
all there are
p!
p(p?1)(p?2)···(p?n
2
+ 1) =
(p?n
2
)!
such matrices,Alternatively,this is the number of n
2
-permutations of a p element
set,which is p!/(p?n
2
)!,
3 Recitation 14
The Tao of BOOKKEEPPER
Problem 2,In this problem,we seek enlightenment through contemplation of the word
BOOKKEEPER,
(a) In how many ways can you arrange the letters in the word POKE?
Solution,There are 4! arrangments corresponding to the 4! permutations of the set
{P,O,K,E},
(b) In how many ways can you arrange the letters in the word BO
1
O
2
K? Observe
that we have subscripted the O’s to make them distinct symbols.
Solution,There are 4! arrangments corresponding to the 4! permutations of the set
{B,O
1
,O
2
,K},
(c) Suppose we map arrangements of the letters in BO
1
O
2
K to arrangements of the
letters in BOOK by erasing the subscripts,Indicate with arrows how the arrange-
ments on the left are mapped to the arrangements on the right,
O
2
BO
1
K
KO
2
BO
1
BOOK
O
1
BO
2
K
OBOK
KO
1
BO
2
KOBO
BO
1
O
2
K
.,,
BO
2
O
1
K
.,,
(d) What kind of mapping is this,young grasshopper?
Solution,2-to-1
(e) In light of the Division Rule,how many arrangements are there of BOOK?
Solution,4!/2
(f) Very good,young master! How many arrangements are there of the letters in
KE
1
E
2
PE
3
R?
Solution,6!
(g) Suppose we map each arrangement of KE
1
E
2
PE
3
Rto an arrangement of KEEPER
by erasing subscripts,List all the different arrangements of KE
1
E
2
PE
3
R that are
mapped to REPEEK in this way,
Solution,RE
1
PE
2
E
3
K,RE
1
PE
3
E
2
K,RE
2
PE
1
E
3
K,RE
2
PE
3
E
1
K,RE
3
PE
1
E
2
K,
RE
3
PE
2
E
1
K
(h) What kind of mapping is this?
Solution,3!-to-1
?
4 Recitation 14
(i) So how many arrangements are there of the letters in KEEPER?
Solution,6!/3!
(j) Now you are ready to face the BOOKKEEPER!
How many arrangements of BO
1
O
2
K
1
K
2
E
1
E
2
PE
3
R are there?
Solution,10!
(k) How many arrangements of BOOK
1
K
2
E
1
E
2
PE
3
R are there?
Solution,10!/2!
(l) How many arrangements of BOOKKE
1
E
2
PE
3
R are there?
Solution,10!/(2! · 2!)
(m) How many arrangements of BOOKKEEPER are there?
Solution,10!/(2! 2! · 3!)
·
(n) How many arrangements of VOODOODOLL are there?
Solution,10!/(2! 2! · 5!)
·
(o) (IMPORTANT) How many n-bit sequences contain k zeros and (n? k) ones?
Solution,n!/(k! · (n? k)!)
This quantity is denoted
n
k
and read,n choose k”,You will see it almost every day
in 6.042 from now until the end of the term,
Remember well what you have learned,subscripts on,subscripts off,
This is the Tao of Bookkeeper,
5 Recitation 14
Problem 3,Solve the following counting problems,De?ne an appropriate mapping (bi-
jective or k-to-1) between a set whose size you know and the set in question,
(a) (IMPORTANT) In how many ways can k elements be chosen from an n-element
set {x
1
,x
2
,...,x
n
}?
Solution,There is a bijection from n-bit sequences with k ones,The sequence
(b
1
,...,b
n
) maps to the subset that contains x
i
if and only if b
i
= 1,Therefore,the
n
number of such subsets is,
k
(b) How many different ways are there to select a dozen donuts if four varieties are
available?
Solution,There is a bijection from selections of a dozen donuts to 15-bit sequences
with exactly 3 ones,In particular,suppose that the varieties are glazed,chocolate,
lemon,and Boston creme,Then a selection of g glazed,c chocolate,l lemon,and b
Boston creme maps to the sequence,
(g 0
s) 1 (c 0
s) 1 (l 0
s) 1 (b 0
s)
Therefore,the number of selections is equal to the number of 15-bit sequences with
exactly 3 ones,which is,
15! 15
=
3! 12! 3
(c) How many paths are there from (0,0) to (10,20) consisting of right-steps (which
increment the?rst coordinate) and up-steps (which increment the second coordi-
nate)?
Solution,There is a bijection from 30-bit sequences with 10 zeros and 20 ones,The
sequence (b
1
,...,b
30
) maps to a path where the i-th step is right if b
i
= 0 and up if
b
i
= 1,Therefore,the number of paths is equal to
30
.
10
(d) An independent living group is hosting eight pre-frosh,affectionately known at
P
1
,...,P
8
by the permanent residents,Each pre-frosh must must be assigned a task,
2 must wash pots,2 must clean the kitchen,1 must clean the bathrooms,1 must
clean the common area,and 2 must serve dinner,In how many ways can P
1
,...,P
8
be put to productive use?
Solution,There is a bijection from sequences containing two P’s,two K’s,a B,a C,
and two D’s,In particular,the sequence (t
1
,...,t
8
) corresponds to assigning P
i
to
washing pots if t
i
= P,to cleaning the kitchen if t
i
= K,to cleaning the bathrooms
if t
i
= B,etc,Therefore,the number of possible assignments is,
8!
2! 2! 1! 1! 2!
6 Recitation 14
(e) In how many ways can Mr,and Mrs,Grumperson distribute 13 indistinguishable
pieces of coal to their two— no,three!— children for Christmas?
Solution,There is a bijection from 15-bit strings with two ones,In particular,the
bit string 0
a
10
b
10
c
maps to the assignment of a coals to the?rst child,b coals to the
second,and c coals to the third,Therefore,there are
15
assignments.
2
(f) How many solutions over the natural numbers are there to the equation,
x
1
+ x
2
+,.,+ x
10
100 ≤
Solution,There is a bijection from 110-bit sequences with 10 ones to solutions to
this equation,In particular,x
i
is the number of zeros before the i-th one but after the
(i? 1)-st one (or the beginning of the sequence),Therefore,there are
110
solutions.
10
(g) (Quiz 2,Fall ’03) Suppose that two identical 52-card decks of are mixed together,
In how many ways can the cards in this double-size deck be arranged?
Solution,The number of sequences of the 104 cards containing 2 of each card is
104!/(2!)
52
,
6.042/18.062J Mathematics for Computer Science April 1,2005
Srini Devadas and Eric Lehman
Notes for Recitation 14
Counting Rules
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
···
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
Rule 2 (Division Rule),If f, A → B is k-to-1,then |A = k B|.| ·|
2 Recitation 14
The Generalized Product Rule
Problem 1,Solve the following counting problems using the generalized product rule,
(a) Next week,I’m going to get really?t! On day 1,I’ll exercise for 5 minutes,On
each subsequent day,I’ll exercise 0,1,2,or 3 minutes more than the previous day,
For example,the number of minutes that I exercise on the seven days of next week
might be 5,6,9,9,9,11,12,How many such sequences are possible?
Solution,The number of minutes on the?rst day can be selected in 1 way,The
number of minutes on each subsequent day can be selected in 4 ways,Therefore,
the number of exercise sequences is 1·4
6
by the extended product rule,
(b) An r-permutation of a set is a sequence of r distinct elements of that set,For
example,here are all the 2-permutations of {a,b,c,d},
(a,b) (a,c) (a,d)
(b,a) (b,c) (b,d)
(c,a) (c,b) (c,d)
(d,a) (d,b) (d,c)
How many r-permutations of an n-element set are there? Express your answer us-
ing factorial notation,
Solution,There are n ways to choose the?rst element,n? 1 ways to choose the
second,n? 2 ways to choose the third,.,,,and there are n? r + 1 ways to choose
the r-th element,Thus,there are,
n!
n·(n?1)·( n?r + 1) =
(n?r)!
n?2)···(
r-permutations of an n-element set,
(c) How many n × n matrices are there with distinct entries drawn from {1,...,p},
where p ≥ n
2
Solution,There are p ways to choose the?rst entry,p?1 ways to choose the second
for each way of choosing the?rst,p? 2 ways of choosing the third,and so forth,In
all there are
p!
p(p?1)(p?2)···(p?n
2
+ 1) =
(p?n
2
)!
such matrices,Alternatively,this is the number of n
2
-permutations of a p element
set,which is p!/(p?n
2
)!,
3 Recitation 14
The Tao of BOOKKEEPPER
Problem 2,In this problem,we seek enlightenment through contemplation of the word
BOOKKEEPER,
(a) In how many ways can you arrange the letters in the word POKE?
Solution,There are 4! arrangments corresponding to the 4! permutations of the set
{P,O,K,E},
(b) In how many ways can you arrange the letters in the word BO
1
O
2
K? Observe
that we have subscripted the O’s to make them distinct symbols.
Solution,There are 4! arrangments corresponding to the 4! permutations of the set
{B,O
1
,O
2
,K},
(c) Suppose we map arrangements of the letters in BO
1
O
2
K to arrangements of the
letters in BOOK by erasing the subscripts,Indicate with arrows how the arrange-
ments on the left are mapped to the arrangements on the right,
O
2
BO
1
K
KO
2
BO
1
BOOK
O
1
BO
2
K
OBOK
KO
1
BO
2
KOBO
BO
1
O
2
K
.,,
BO
2
O
1
K
.,,
(d) What kind of mapping is this,young grasshopper?
Solution,2-to-1
(e) In light of the Division Rule,how many arrangements are there of BOOK?
Solution,4!/2
(f) Very good,young master! How many arrangements are there of the letters in
KE
1
E
2
PE
3
R?
Solution,6!
(g) Suppose we map each arrangement of KE
1
E
2
PE
3
Rto an arrangement of KEEPER
by erasing subscripts,List all the different arrangements of KE
1
E
2
PE
3
R that are
mapped to REPEEK in this way,
Solution,RE
1
PE
2
E
3
K,RE
1
PE
3
E
2
K,RE
2
PE
1
E
3
K,RE
2
PE
3
E
1
K,RE
3
PE
1
E
2
K,
RE
3
PE
2
E
1
K
(h) What kind of mapping is this?
Solution,3!-to-1
?
4 Recitation 14
(i) So how many arrangements are there of the letters in KEEPER?
Solution,6!/3!
(j) Now you are ready to face the BOOKKEEPER!
How many arrangements of BO
1
O
2
K
1
K
2
E
1
E
2
PE
3
R are there?
Solution,10!
(k) How many arrangements of BOOK
1
K
2
E
1
E
2
PE
3
R are there?
Solution,10!/2!
(l) How many arrangements of BOOKKE
1
E
2
PE
3
R are there?
Solution,10!/(2! · 2!)
(m) How many arrangements of BOOKKEEPER are there?
Solution,10!/(2! 2! · 3!)
·
(n) How many arrangements of VOODOODOLL are there?
Solution,10!/(2! 2! · 5!)
·
(o) (IMPORTANT) How many n-bit sequences contain k zeros and (n? k) ones?
Solution,n!/(k! · (n? k)!)
This quantity is denoted
n
k
and read,n choose k”,You will see it almost every day
in 6.042 from now until the end of the term,
Remember well what you have learned,subscripts on,subscripts off,
This is the Tao of Bookkeeper,
5 Recitation 14
Problem 3,Solve the following counting problems,De?ne an appropriate mapping (bi-
jective or k-to-1) between a set whose size you know and the set in question,
(a) (IMPORTANT) In how many ways can k elements be chosen from an n-element
set {x
1
,x
2
,...,x
n
}?
Solution,There is a bijection from n-bit sequences with k ones,The sequence
(b
1
,...,b
n
) maps to the subset that contains x
i
if and only if b
i
= 1,Therefore,the
n
number of such subsets is,
k
(b) How many different ways are there to select a dozen donuts if four varieties are
available?
Solution,There is a bijection from selections of a dozen donuts to 15-bit sequences
with exactly 3 ones,In particular,suppose that the varieties are glazed,chocolate,
lemon,and Boston creme,Then a selection of g glazed,c chocolate,l lemon,and b
Boston creme maps to the sequence,
(g 0
s) 1 (c 0
s) 1 (l 0
s) 1 (b 0
s)
Therefore,the number of selections is equal to the number of 15-bit sequences with
exactly 3 ones,which is,
15! 15
=
3! 12! 3
(c) How many paths are there from (0,0) to (10,20) consisting of right-steps (which
increment the?rst coordinate) and up-steps (which increment the second coordi-
nate)?
Solution,There is a bijection from 30-bit sequences with 10 zeros and 20 ones,The
sequence (b
1
,...,b
30
) maps to a path where the i-th step is right if b
i
= 0 and up if
b
i
= 1,Therefore,the number of paths is equal to
30
.
10
(d) An independent living group is hosting eight pre-frosh,affectionately known at
P
1
,...,P
8
by the permanent residents,Each pre-frosh must must be assigned a task,
2 must wash pots,2 must clean the kitchen,1 must clean the bathrooms,1 must
clean the common area,and 2 must serve dinner,In how many ways can P
1
,...,P
8
be put to productive use?
Solution,There is a bijection from sequences containing two P’s,two K’s,a B,a C,
and two D’s,In particular,the sequence (t
1
,...,t
8
) corresponds to assigning P
i
to
washing pots if t
i
= P,to cleaning the kitchen if t
i
= K,to cleaning the bathrooms
if t
i
= B,etc,Therefore,the number of possible assignments is,
8!
2! 2! 1! 1! 2!
6 Recitation 14
(e) In how many ways can Mr,and Mrs,Grumperson distribute 13 indistinguishable
pieces of coal to their two— no,three!— children for Christmas?
Solution,There is a bijection from 15-bit strings with two ones,In particular,the
bit string 0
a
10
b
10
c
maps to the assignment of a coals to the?rst child,b coals to the
second,and c coals to the third,Therefore,there are
15
assignments.
2
(f) How many solutions over the natural numbers are there to the equation,
x
1
+ x
2
+,.,+ x
10
100 ≤
Solution,There is a bijection from 110-bit sequences with 10 ones to solutions to
this equation,In particular,x
i
is the number of zeros before the i-th one but after the
(i? 1)-st one (or the beginning of the sequence),Therefore,there are
110
solutions.
10
(g) (Quiz 2,Fall ’03) Suppose that two identical 52-card decks of are mixed together,
In how many ways can the cards in this double-size deck be arranged?
Solution,The number of sequences of the 104 cards containing 2 of each card is
104!/(2!)
52
,
