6.042/18.062J Mathematics for Computer Science March 29,2005
Srini Devadas and Eric Lehman
Problem Set 7 Solutions
Due,Monday,April 4 at 9 PM
Problem 1,Every function has some subset of these properties,
injective surjective bijective
Determine the properties of the functions below,and brie?y explain your reasoning,
x
(a) The function f, R R de?ned by f(x) = e,→
Solution,This function is injective,since e
x
takes on each nonnegative real value
for exactly one x,However,the function is not surjective,because e
x
never takes on
negative values,Therefore,the function is not bijective either,
x
(b) The function f, R R
+
de?ned by f(x) = e,→
Solution,The function e
x
takes on every nonnegative value for exactly one x,so it
is injective,surjective,and bijective,
(c) The function f, R → R de?ned by f(x) = (x + 1)x(x? 1),
Solution,This function is surjective,since it is continuous,it tends to +∞ for large
positive x,and tends to?∞ for large negative x,Thus,the function takes on each
real value for at least one x,However,this function is not injective,since it takes
on the value 0 at x =?1,x = 0,and x = 1,Therefore,the function is not bijective
either,
(d) Let S be the set of all 20-bit sequences,Let T be the set of all 10-bit sequences,Let
f, S T map each 20-bit sequence to its?rst 10 bits,For example,→
f(11110110101101010010) = 1111011010
Solution,This function is surjective since the sequence b
1
b
2
...b
10
is mapped to by
b
1
b
2
...b
10
00,..0,for example,However,the function is not injective,because this
sequence is also mapped to by b
1
b
2
...b
10
11,..1,Consequently,the function is not
bijective either,
Problem 2,There are 20 books arranged in a row on a shelf,
2 Problem Set 7
(a) Describe a bijection between ways of choosing 6 of these books so that no two
adjacent books are selected and 15-bit sequences with exactly 6 ones,
Solution,There is a bijection from 15-bit sequences with exactly six 1’s to valid book
selections,given such a sequence,map each zero to a non-chosen book,each of the
rst?ve 1’s to a chosen book followed by a non-chosen book,and the last 1 to a
chosen book,For example,here is a con?guration of books and the corresponding
binary sequence,
1
0
0
10
0
10
0
0
110
0
1
Selected books are darkened,Notice that the?rst?ves ones are mapped to a chosen
book and an non-chosen book in order to ensure that the binary sequence maps to a
valid selection of books,
(b) How many ways are there to select 6 books so that no two adjacent books are
selected?
Solution,By the Bijection Rule,this is equal to the number of 15-bit sequences with
exactly 6 ones,which is equal to
15! 15
=
6! 9! 6
by the Bookkeeper Rule,
Problem 3,Answer the following questions and provide brief justi?cations,Not every
problem can be solved with a cute formula; you may have to fall back on case analysis,
explicit enumeration,or ad hoc methods,
You may leave factorials and binomial coef?cients in your answers,
(a) In how many different ways can the letters in the name of the popular 1980’s
band BANANARAMA be arranged?
Solution,There are 5 A’s,2 N’s,1 B,1 R,and 1 M,Therefore,the number of
arrangements is
10!
5! 2! 1! 1! 1!
by the Bookkeeper Rule,
(b) How many different paths are there from point (0,0,0) to point (12,24,36) if ev-
ery step increments one coordinate and leaves the other two unchanged?
Solution,There is a bijection between the set of all such paths and the set of strings
containing 12 X’s,24 Y’s,and 36 Z’s,In particular,we obtain a path by working
3 Problem Set 7
through a string from left to right,An X corresponds to a step that increments the
rst coordinate,a Y increments the second coordinate,and a Z increments the third,
The number of such strings is,
72!
12! 24! 36!
Therefore,this is also the number of paths,
(c) In how many different ways can 2n students be paired up?
Solution,Pair up students by the following procedure,Line up the students and
pair the?rst and second,the third and fourth,the?fth and sixth,etc,The students
can be lined up in (2n)! ways,However,this overcounts by a factor of 2
n
,because we
would get the same pairing if the?rst and second students were swapped,the third
and fourth were swapped,etc,Furthermore,we are still overcounting by a factor of
n!,because we would get the same pairing even if pairs of students were permuted,
e.g,the?rst and second were swapped with the ninth and tenth,Therefore,the
number of pairings is,
(2n)!
2
n
n!·
(d) How many different solutions over the natural numbers are there to the follow-
ing equation?
x
1
+ x
2
+ x
3
+,.,+ x
8
= 100
A solution is a speci?cation of the value of each variable x
i
,Two solutions are dif-
ferent if different values are speci?ed for some variable x
i
,
Solution,There is a bijection between sequences containing 100 zeros and 7 ones,
Speci?cally,the 7 ones divide the zeros into 8 segments,Let x
i
be the number of
zeros in the i-th segment,Therefore,the number of solutions is,
100 + 7
7
(e) In how many different ways can one choose n out of 2n objects,given that n of
the 2n objects are identical and the other n are all unique?
Solution,We can select n objects as follows,First,take a subset of the unique
objects,Then take however many identical elements are needed to bring the total to
n,The?rst step can be done in 2
n
ways,and the second can be done in only 1 way,
Therefore,there are 2
n
ways to choose n objects,
(f) How many undirected graphs are there with vertices v
1
,v
2
,...,v
n
if self-loops are
permitted?
n
Solution,There are + n potential edges,each of which may or may not appear
2
in a given graph,Therefore,the number of graphs is,
2
(
n
2
)
+n
- - -
@? @?
4 Problem Set 7
(g) In how many different ways can 10 indistinguishable balls be placed in four dis-
tinguishable boxes,such that every box gets 1,2,3,or 4 balls?
Solution,First,we might as well put 1 ball in every box,Now the problem is to put
the remaining 6 balls into 4 boxes so that no box gets more than 3 balls,Now we
turn to case analysis,For example,we could put 3 balls in two boxes and 0 balls in
the other two boxes,There are
4!
= 6 ways to do this,All cases are listed below,
2! 2!
distribution of balls # of ways
4!
3,3,0,0
2! 2!
= 6
4!
= 243,2,1,0
1! 1! 1! 1!
4!
3,1,1,1
3! 1!
= 4
4!
2,2,2,0
3! 1!
= 4
4!
2,2,1,1
2! 2!
= 6
Thus,there are 6 + 24 + 4 + 4 + 6 = 44 ways in all,
(h) There are 15 sidewalk squares in a row,Suppose that a ball can be thrown so that
it bounces on 0,1,2,or 3 distinct sidewalk squares,Assume that the ball always
moves from left to right,How many different throws are possible? As an example,
a two-bounce throw is illustrated below,
@ R? R? @
Solution.
15 15 15 15
+ + +
0 1 2 3
(i) In how many different ways can the numbers shown on a red die,a green die,
and a blue die total up to 15? Assume that these are ordinary 6-sided dice,
Solution,We fall back on explicit enumeration,Let R,G,and B be the values shown
on the three dice,
R = 1,B + G = 14 → 0 ways
R = 2,B + G = 13 → 0 ways
R = 3,B + G = 12 → 1 way
R = 4,B + G = 11 → 2 ways
R = 5,B + G = 10 → 3 ways
R = 6,B + G = 9 → 4 ways
(j) The working days in the next year can be numbered 1,2,3,.,,,300,I’d like to
avoid as many as possible,
5 Problem Set 7
On even-numbered days,I’ll say I’m sick,
On days that are a multiple of 3,I’ll say I was stuck in traf?c,
On days that are a multiple of 5,I’ll refuse to come out from under the blankets,
In total,how many work days will I avoid in the coming year?
Solution,Let D
2
be the set of even-numbered days,D
3
be the days that are a mul-
tiple of 3,and D
5
be days that are a multiple of 5,The set of days I can avoid is
D
2
∪ D
3
∪ D
5
,By the Inclusion-Exclusion Rule,the size of this set is,
D
2
∪ D
3
∪ D
5
= D
2
| + D
3
+ D
5
| | | | | | |
D
2
∩ D
3
D
2
∩ D
5
D
3
∩ D
5
| |?| |?| |
+ D
2
∩ D
3
∩ D
5
| |
300 300 300 300 300 300 300
=
2
+
3
+
5
2 3
2 5
3 5
+
2 3 5· · · · ·
= 220
Problem 4,Use the pigeonhole principle to solve the following problems,
(a) Prove that among any n
2
+ 1 points within an n× n square there must exist two
points whose distance is at most
√
2,
Solution,Partition the n × n into n
2
unit squares,Each of the n
2
+ 1 points lies
in one of these n
2
unit squares,(If a point lies on the boundary between squares,
assign it to a square arbitrarily.) Therefore,by the pigeonhole principle,there exist
two points in the same unit square,And the distance between those two points can
be at most
√
2,
(b) Jellybeans of 6 different?avors are stored in 5 jars,There are 11 jellybeans of each
avor,Prove that some jar contains at least three jellybeans of one?avor and also at
least three jellybeans of some other?avor,
Solution,We use the pigeonhole principle twice,Since there are 11 beans of a given
avor and there are only 5 jars,some jar must get at least?11/5?= 3 beans of that
avor,Since there are 6?avors and only 5 jars,some jar must get two pairs of same-
avored beans,
(c) Prove that among every set of 30 integers,there exist two whose difference or sum
is a multiple of 51,
Solution,Regard the 30 integers as pigeons,Regard the 26 sets {0},{1,50},{2,49},
...,{25,26} as pigeonholes,Map integer n to the set containing n rem 51,By the
pigeonhole principle,some two pigeons (integers a and b) are mapped to the same
pigeonhole,Thus,either,
a rem 51 = b rem 51 and so the difference of a and b is a multiple of 51,
6 Problem Set 7
a rem 51 + b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of
51,
Problem 5,A balanced parentheses string is a sequence of left and right parentheses such
that
the total number of left and right parentheses is equal,and
the number of left parentheses is greater than or equal to the number of right paren-
theses in every pre?x,
For example,
Balanced Not Balanced
(()) ((() more left than right
()(()) ())()( fewer left than right in pre?x ())
Let C
n
be the number of balanced parentheses strings with 2n parentheses,The values
C
0
,C
1
,C
2
,..,are the Catalan numbers,which come up in dozens of different counting
problems,Here are the?rst few Catalan numbers,
n 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 C
n
(a) Verify the?rst four entries by listing all balanced parentheses strings with at most
6 parentheses,(Don’t forget the empty string!)
Solution,Here are all the balanced parentheses strings with at most 6 parentheses,
empty () ()() (())
()(()) (())() (()()) ((())) ()()()
Therefore,C
0
= 1,C
1
= 1,C
2
= 2,and C
3
= 5 as claimed in the table,
(b) A path from (0,0) to (n,n) consisting of unit steps upward or rightward is safe if
it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death,
7 Problem Set 7
Flami
Chasm of
ng
Hideous
Death
Fl
C
ami
has
ng
m of
Hideous
Death
A Safe Path An Unsafe Path
Show that there are exactly C
n
safe paths by describing a bijection with balanced
parentheses strings,
(c) Many computational geometry algorithms begin by partitioning polygons into
triangles with the same vertices,For example,here are all the possible triangulations
of a pentagon,
B
B
Q
Q
Q
Q
Q
Q
Q
Q
B
B
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
B
B
c B
CC
c
C
B
C
#
C
#
C
c
B C
c
C B C
#
C
#
C
c
c
B C
c
C B C
#
#
C
#
#
C
c
B C
c
c
C B C
#
C
#
C cB C c C B C# C#
Show that there are C
n
different ways to triangulate a convex (n+2)-gon by describ-
ing a bijection from triangulations to balanced parentheses strings,(This problem is
challenging; ask your TA for help if you’re stuck!)
Solution,Note that every nonempty balanced parentheses string has the form (α)β
since the?rst symbol must be ( and there must be a matching ),Thus,every bal-
anced parentheses string can be decomposed into two smaller strings α and β,We’ll
exploit this fact to recursively map a balanced parentheses string to a triangulation,
Suppose we have a not-yet-triangulated (n + 2)-gon and a balanced parentheses
string (α)β,We must map the parentheses string to a triangulation,
Select two consecutive vertices x and y and denote the remaining vertices v
0
,.,,,
v
n?1
,It must be that α contains j pairs of parentheses and β contains the remaining
(n? 1)? j pairs for some j between 0 and n? 1,Draw a triangle with the vertices
x,y,and v
j
,
| |?
8 Problem Set 7
x y
v0
v1
v2
v3 v4
v5
v6
v7
This triangle partitions the polygon into a (j + 2)-gon and a (n?j + 1)-gon,Trian-
gulate these polygons recursively using the balanced parentheses strings α and β,
(Let x and v
j
play the role of x and y in triangulation one side,and let v
j
and y play
the role of x and y on the other.)
Problem 6,A derangement is a permutation (x
1
,x
2
,...,x
n
) of the set {1,2,...,n}such that
x
i
=? i for all i,For example,(2,3,4,5,1) is a derangement,but (2,1,3,5,4) is not because
3 appears in the third position,The objective of this problem is to count derangements,
(a) Let’s?rst work on counting permutations of {1,2,...,n} that are not derange-
ments,Let S
i
be the set of all permutations (x
1
,x
2
,...,x
n
) of the set {1,2,...,n}
such that x
i
= i,Use the inclusion-exclusion formula to express the number of
non-derangements in terms of sizes of intersections of the sets S
1
,...,S
n
,
Solution,
S
i
∩S
j
+ S
i
∩S
j
∩S
k
...± S
1
∩S
2
∩...∩S
n
|S
i
|? | | | | |
i i,j
|
i,j,k
In each summation,the subscripts are distinct elements of {1,...,n},
(b) What is |S
i
|
Solution,There is a bijection between permutations of {1,2,...,n}with i in the i-th
position and unrestricted permutations of {1,2,...,n}?i,Therefore,S
i
= (n?1)!.| |
(c) What is S
i
∩S
j
where i = j?
Solution,The set S
i
∩S
j
consists of all permutations with i in the i-th position and
j in the j-th position,Thus,there is a bijection with permutations of {1,2,...,n}?
{i,j},and so S
i
∩S
j
= (n?2)!.| |
(d) What is S
i
1
∩S
i
2
∩...∩S
i
k
where i
1
,i
2
,...,i
k
are all distinct? | |
Solution,By the same argument,(n?k)!,
9 Problem Set 7
(e) How many terms in the expression in part (a) have the form S
i
1
∩ S
i
2
∩,..∩ S
i
k
| |
Solution,There is one such term for each k-element subset of the n-element set
n
{1,2,...,n},Therefore,there are such terms,
k
(f) Combine your answers to the preceding parts to get a (messy) expression for the
number of non-derangements,
Solution,
S
i
∩ S
j
+ S
i
∩ S
j
∩ S
k
,..± S
1
∩ S
2
∩,..∩ S
n
|S
i
|? | | | | |
i i,j
|
i,j,k
n n n n
=
1
· (n? 1)!?
2
· (n? 2)! +
3
· (n? 3)!?,..±
n
· 0!
1 1 1 1
= n!
1!
2!
+
3!
,..±
n!
(g) Now give an expression for the number of derangements,
Solution,
1 1 1 1
n! 1? +
3!
,..±
1!
2! n!
(h) As n goes to in?nity,this expression approaches a constant fraction of all permu-
tations,What is that constant? Recall that,
2 3
x x
x
e = 1 + x + + +,.,
2! 3!
Solution,1/e
Srini Devadas and Eric Lehman
Problem Set 7 Solutions
Due,Monday,April 4 at 9 PM
Problem 1,Every function has some subset of these properties,
injective surjective bijective
Determine the properties of the functions below,and brie?y explain your reasoning,
x
(a) The function f, R R de?ned by f(x) = e,→
Solution,This function is injective,since e
x
takes on each nonnegative real value
for exactly one x,However,the function is not surjective,because e
x
never takes on
negative values,Therefore,the function is not bijective either,
x
(b) The function f, R R
+
de?ned by f(x) = e,→
Solution,The function e
x
takes on every nonnegative value for exactly one x,so it
is injective,surjective,and bijective,
(c) The function f, R → R de?ned by f(x) = (x + 1)x(x? 1),
Solution,This function is surjective,since it is continuous,it tends to +∞ for large
positive x,and tends to?∞ for large negative x,Thus,the function takes on each
real value for at least one x,However,this function is not injective,since it takes
on the value 0 at x =?1,x = 0,and x = 1,Therefore,the function is not bijective
either,
(d) Let S be the set of all 20-bit sequences,Let T be the set of all 10-bit sequences,Let
f, S T map each 20-bit sequence to its?rst 10 bits,For example,→
f(11110110101101010010) = 1111011010
Solution,This function is surjective since the sequence b
1
b
2
...b
10
is mapped to by
b
1
b
2
...b
10
00,..0,for example,However,the function is not injective,because this
sequence is also mapped to by b
1
b
2
...b
10
11,..1,Consequently,the function is not
bijective either,
Problem 2,There are 20 books arranged in a row on a shelf,
2 Problem Set 7
(a) Describe a bijection between ways of choosing 6 of these books so that no two
adjacent books are selected and 15-bit sequences with exactly 6 ones,
Solution,There is a bijection from 15-bit sequences with exactly six 1’s to valid book
selections,given such a sequence,map each zero to a non-chosen book,each of the
rst?ve 1’s to a chosen book followed by a non-chosen book,and the last 1 to a
chosen book,For example,here is a con?guration of books and the corresponding
binary sequence,
1
0
0
10
0
10
0
0
110
0
1
Selected books are darkened,Notice that the?rst?ves ones are mapped to a chosen
book and an non-chosen book in order to ensure that the binary sequence maps to a
valid selection of books,
(b) How many ways are there to select 6 books so that no two adjacent books are
selected?
Solution,By the Bijection Rule,this is equal to the number of 15-bit sequences with
exactly 6 ones,which is equal to
15! 15
=
6! 9! 6
by the Bookkeeper Rule,
Problem 3,Answer the following questions and provide brief justi?cations,Not every
problem can be solved with a cute formula; you may have to fall back on case analysis,
explicit enumeration,or ad hoc methods,
You may leave factorials and binomial coef?cients in your answers,
(a) In how many different ways can the letters in the name of the popular 1980’s
band BANANARAMA be arranged?
Solution,There are 5 A’s,2 N’s,1 B,1 R,and 1 M,Therefore,the number of
arrangements is
10!
5! 2! 1! 1! 1!
by the Bookkeeper Rule,
(b) How many different paths are there from point (0,0,0) to point (12,24,36) if ev-
ery step increments one coordinate and leaves the other two unchanged?
Solution,There is a bijection between the set of all such paths and the set of strings
containing 12 X’s,24 Y’s,and 36 Z’s,In particular,we obtain a path by working
3 Problem Set 7
through a string from left to right,An X corresponds to a step that increments the
rst coordinate,a Y increments the second coordinate,and a Z increments the third,
The number of such strings is,
72!
12! 24! 36!
Therefore,this is also the number of paths,
(c) In how many different ways can 2n students be paired up?
Solution,Pair up students by the following procedure,Line up the students and
pair the?rst and second,the third and fourth,the?fth and sixth,etc,The students
can be lined up in (2n)! ways,However,this overcounts by a factor of 2
n
,because we
would get the same pairing if the?rst and second students were swapped,the third
and fourth were swapped,etc,Furthermore,we are still overcounting by a factor of
n!,because we would get the same pairing even if pairs of students were permuted,
e.g,the?rst and second were swapped with the ninth and tenth,Therefore,the
number of pairings is,
(2n)!
2
n
n!·
(d) How many different solutions over the natural numbers are there to the follow-
ing equation?
x
1
+ x
2
+ x
3
+,.,+ x
8
= 100
A solution is a speci?cation of the value of each variable x
i
,Two solutions are dif-
ferent if different values are speci?ed for some variable x
i
,
Solution,There is a bijection between sequences containing 100 zeros and 7 ones,
Speci?cally,the 7 ones divide the zeros into 8 segments,Let x
i
be the number of
zeros in the i-th segment,Therefore,the number of solutions is,
100 + 7
7
(e) In how many different ways can one choose n out of 2n objects,given that n of
the 2n objects are identical and the other n are all unique?
Solution,We can select n objects as follows,First,take a subset of the unique
objects,Then take however many identical elements are needed to bring the total to
n,The?rst step can be done in 2
n
ways,and the second can be done in only 1 way,
Therefore,there are 2
n
ways to choose n objects,
(f) How many undirected graphs are there with vertices v
1
,v
2
,...,v
n
if self-loops are
permitted?
n
Solution,There are + n potential edges,each of which may or may not appear
2
in a given graph,Therefore,the number of graphs is,
2
(
n
2
)
+n
- - -
@? @?
4 Problem Set 7
(g) In how many different ways can 10 indistinguishable balls be placed in four dis-
tinguishable boxes,such that every box gets 1,2,3,or 4 balls?
Solution,First,we might as well put 1 ball in every box,Now the problem is to put
the remaining 6 balls into 4 boxes so that no box gets more than 3 balls,Now we
turn to case analysis,For example,we could put 3 balls in two boxes and 0 balls in
the other two boxes,There are
4!
= 6 ways to do this,All cases are listed below,
2! 2!
distribution of balls # of ways
4!
3,3,0,0
2! 2!
= 6
4!
= 243,2,1,0
1! 1! 1! 1!
4!
3,1,1,1
3! 1!
= 4
4!
2,2,2,0
3! 1!
= 4
4!
2,2,1,1
2! 2!
= 6
Thus,there are 6 + 24 + 4 + 4 + 6 = 44 ways in all,
(h) There are 15 sidewalk squares in a row,Suppose that a ball can be thrown so that
it bounces on 0,1,2,or 3 distinct sidewalk squares,Assume that the ball always
moves from left to right,How many different throws are possible? As an example,
a two-bounce throw is illustrated below,
@ R? R? @
Solution.
15 15 15 15
+ + +
0 1 2 3
(i) In how many different ways can the numbers shown on a red die,a green die,
and a blue die total up to 15? Assume that these are ordinary 6-sided dice,
Solution,We fall back on explicit enumeration,Let R,G,and B be the values shown
on the three dice,
R = 1,B + G = 14 → 0 ways
R = 2,B + G = 13 → 0 ways
R = 3,B + G = 12 → 1 way
R = 4,B + G = 11 → 2 ways
R = 5,B + G = 10 → 3 ways
R = 6,B + G = 9 → 4 ways
(j) The working days in the next year can be numbered 1,2,3,.,,,300,I’d like to
avoid as many as possible,
5 Problem Set 7
On even-numbered days,I’ll say I’m sick,
On days that are a multiple of 3,I’ll say I was stuck in traf?c,
On days that are a multiple of 5,I’ll refuse to come out from under the blankets,
In total,how many work days will I avoid in the coming year?
Solution,Let D
2
be the set of even-numbered days,D
3
be the days that are a mul-
tiple of 3,and D
5
be days that are a multiple of 5,The set of days I can avoid is
D
2
∪ D
3
∪ D
5
,By the Inclusion-Exclusion Rule,the size of this set is,
D
2
∪ D
3
∪ D
5
= D
2
| + D
3
+ D
5
| | | | | | |
D
2
∩ D
3
D
2
∩ D
5
D
3
∩ D
5
| |?| |?| |
+ D
2
∩ D
3
∩ D
5
| |
300 300 300 300 300 300 300
=
2
+
3
+
5
2 3
2 5
3 5
+
2 3 5· · · · ·
= 220
Problem 4,Use the pigeonhole principle to solve the following problems,
(a) Prove that among any n
2
+ 1 points within an n× n square there must exist two
points whose distance is at most
√
2,
Solution,Partition the n × n into n
2
unit squares,Each of the n
2
+ 1 points lies
in one of these n
2
unit squares,(If a point lies on the boundary between squares,
assign it to a square arbitrarily.) Therefore,by the pigeonhole principle,there exist
two points in the same unit square,And the distance between those two points can
be at most
√
2,
(b) Jellybeans of 6 different?avors are stored in 5 jars,There are 11 jellybeans of each
avor,Prove that some jar contains at least three jellybeans of one?avor and also at
least three jellybeans of some other?avor,
Solution,We use the pigeonhole principle twice,Since there are 11 beans of a given
avor and there are only 5 jars,some jar must get at least?11/5?= 3 beans of that
avor,Since there are 6?avors and only 5 jars,some jar must get two pairs of same-
avored beans,
(c) Prove that among every set of 30 integers,there exist two whose difference or sum
is a multiple of 51,
Solution,Regard the 30 integers as pigeons,Regard the 26 sets {0},{1,50},{2,49},
...,{25,26} as pigeonholes,Map integer n to the set containing n rem 51,By the
pigeonhole principle,some two pigeons (integers a and b) are mapped to the same
pigeonhole,Thus,either,
a rem 51 = b rem 51 and so the difference of a and b is a multiple of 51,
6 Problem Set 7
a rem 51 + b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of
51,
Problem 5,A balanced parentheses string is a sequence of left and right parentheses such
that
the total number of left and right parentheses is equal,and
the number of left parentheses is greater than or equal to the number of right paren-
theses in every pre?x,
For example,
Balanced Not Balanced
(()) ((() more left than right
()(()) ())()( fewer left than right in pre?x ())
Let C
n
be the number of balanced parentheses strings with 2n parentheses,The values
C
0
,C
1
,C
2
,..,are the Catalan numbers,which come up in dozens of different counting
problems,Here are the?rst few Catalan numbers,
n 0 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 C
n
(a) Verify the?rst four entries by listing all balanced parentheses strings with at most
6 parentheses,(Don’t forget the empty string!)
Solution,Here are all the balanced parentheses strings with at most 6 parentheses,
empty () ()() (())
()(()) (())() (()()) ((())) ()()()
Therefore,C
0
= 1,C
1
= 1,C
2
= 2,and C
3
= 5 as claimed in the table,
(b) A path from (0,0) to (n,n) consisting of unit steps upward or rightward is safe if
it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death,
7 Problem Set 7
Flami
Chasm of
ng
Hideous
Death
Fl
C
ami
has
ng
m of
Hideous
Death
A Safe Path An Unsafe Path
Show that there are exactly C
n
safe paths by describing a bijection with balanced
parentheses strings,
(c) Many computational geometry algorithms begin by partitioning polygons into
triangles with the same vertices,For example,here are all the possible triangulations
of a pentagon,
B
B
Q
Q
Q
Q
Q
Q
Q
Q
B
B
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
B
B
c B
CC
c
C
B
C
#
C
#
C
c
B C
c
C B C
#
C
#
C
c
c
B C
c
C B C
#
#
C
#
#
C
c
B C
c
c
C B C
#
C
#
C cB C c C B C# C#
Show that there are C
n
different ways to triangulate a convex (n+2)-gon by describ-
ing a bijection from triangulations to balanced parentheses strings,(This problem is
challenging; ask your TA for help if you’re stuck!)
Solution,Note that every nonempty balanced parentheses string has the form (α)β
since the?rst symbol must be ( and there must be a matching ),Thus,every bal-
anced parentheses string can be decomposed into two smaller strings α and β,We’ll
exploit this fact to recursively map a balanced parentheses string to a triangulation,
Suppose we have a not-yet-triangulated (n + 2)-gon and a balanced parentheses
string (α)β,We must map the parentheses string to a triangulation,
Select two consecutive vertices x and y and denote the remaining vertices v
0
,.,,,
v
n?1
,It must be that α contains j pairs of parentheses and β contains the remaining
(n? 1)? j pairs for some j between 0 and n? 1,Draw a triangle with the vertices
x,y,and v
j
,
| |?
8 Problem Set 7
x y
v0
v1
v2
v3 v4
v5
v6
v7
This triangle partitions the polygon into a (j + 2)-gon and a (n?j + 1)-gon,Trian-
gulate these polygons recursively using the balanced parentheses strings α and β,
(Let x and v
j
play the role of x and y in triangulation one side,and let v
j
and y play
the role of x and y on the other.)
Problem 6,A derangement is a permutation (x
1
,x
2
,...,x
n
) of the set {1,2,...,n}such that
x
i
=? i for all i,For example,(2,3,4,5,1) is a derangement,but (2,1,3,5,4) is not because
3 appears in the third position,The objective of this problem is to count derangements,
(a) Let’s?rst work on counting permutations of {1,2,...,n} that are not derange-
ments,Let S
i
be the set of all permutations (x
1
,x
2
,...,x
n
) of the set {1,2,...,n}
such that x
i
= i,Use the inclusion-exclusion formula to express the number of
non-derangements in terms of sizes of intersections of the sets S
1
,...,S
n
,
Solution,
S
i
∩S
j
+ S
i
∩S
j
∩S
k
...± S
1
∩S
2
∩...∩S
n
|S
i
|? | | | | |
i i,j
|
i,j,k
In each summation,the subscripts are distinct elements of {1,...,n},
(b) What is |S
i
|
Solution,There is a bijection between permutations of {1,2,...,n}with i in the i-th
position and unrestricted permutations of {1,2,...,n}?i,Therefore,S
i
= (n?1)!.| |
(c) What is S
i
∩S
j
where i = j?
Solution,The set S
i
∩S
j
consists of all permutations with i in the i-th position and
j in the j-th position,Thus,there is a bijection with permutations of {1,2,...,n}?
{i,j},and so S
i
∩S
j
= (n?2)!.| |
(d) What is S
i
1
∩S
i
2
∩...∩S
i
k
where i
1
,i
2
,...,i
k
are all distinct? | |
Solution,By the same argument,(n?k)!,
9 Problem Set 7
(e) How many terms in the expression in part (a) have the form S
i
1
∩ S
i
2
∩,..∩ S
i
k
| |
Solution,There is one such term for each k-element subset of the n-element set
n
{1,2,...,n},Therefore,there are such terms,
k
(f) Combine your answers to the preceding parts to get a (messy) expression for the
number of non-derangements,
Solution,
S
i
∩ S
j
+ S
i
∩ S
j
∩ S
k
,..± S
1
∩ S
2
∩,..∩ S
n
|S
i
|? | | | | |
i i,j
|
i,j,k
n n n n
=
1
· (n? 1)!?
2
· (n? 2)! +
3
· (n? 3)!?,..±
n
· 0!
1 1 1 1
= n!
1!
2!
+
3!
,..±
n!
(g) Now give an expression for the number of derangements,
Solution,
1 1 1 1
n! 1? +
3!
,..±
1!
2! n!
(h) As n goes to in?nity,this expression approaches a constant fraction of all permu-
tations,What is that constant? Recall that,
2 3
x x
x
e = 1 + x + + +,.,
2! 3!
Solution,1/e
