Massachusetts Institute of Technology Handout 53 6.042J/18.062J: Mathematics for Computer Science November 13, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 8 Solutions

Read sections 4.3, 4.4, and Appendix 3 in Rosen.

Problem 1. (15 points) Solve the following counting problems. Simplifying expressions is unnecessary.

(a) Find the number of 5-card hands with consecutive values, e. g. 8♣ 9♡ 10♢ J♢ Q♠. (Assume that the value of an ace is just above the value of a king.)

There are 9 possible sequences of five consecutive values. For each sequence, there are 4^{5} hands, since each value can be represented by one of four different suits. Therefore, there are a total of 9 · 4^{5} such hands.

(b) Find the number of 5-card hands with exactly three aces.

We can choose the three aces in \binom{4}{3} ways, and we can choose the remaining two cards in \binom{48}{2} ways. Thus, there are \binom{4}{3}\binom{48}{2} such hands.

(c) Find the number of 5-card hands in which every suit appears at most twice.

There are two cases. Either one suit appears twice or else two suits appear twice. The number of hands in which one suit appears twice is \binom{13}{2}·13^{3} ·4. The number of hands in which two suits appear twice is \binom{13}{2}^{2} · 13 · 12. Therefore, there are a total of

\binom{13}{2} · 13^{3} · 4 + \binom{13}{2}^{2} · 13 · 12

such hands.

(d) There are 15 sidewalk squares in front of the Lab for Computer Science. Suppose that Theory Pig can be thrown so that he bounces on 0, 1, 2, or 3 distinct sidewalk squares. How many different throws are possible?

\binom{15}{0} + \binom{15}{1} + \binom{15}{2} + \binom{15}{3}

(e) 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.

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

Thus there are 10 ways in total.

(f) How many permutations are there of the letters MISSISSIP P I?

\frac{11!}{4! 4! 2!} = 34650

(g) Find the number of squences of k non-negative integers with sum equal to n. For example, if k = 2 and n = 3, then there are four sequences: 0 + 3, 1 + 2, 2 + 1, and 3 + 0.

This is equal to the number of strings with n stars and k − 1 bars. The sizes of the k groups of stars are the values of the k integers in the sequence. Thus, there are

\binom{n + k − 1}{n}

such sequences.

(h) Find the number of squences of k positive integers with sum equal to n. For example, if k = 2 and n = 4, then there are three sequences: 1 + 3, 2 + 2, and 3 + 1.

This is equal to the number of strings with n − k stars and k − 1 bars. Numbers in the sequence are one greater than the sizes of the groups of stars. Thus, there are

\binom{n − 1}{k − 1}

sequences.

Problem 2. (10 points) Solve the following counting problems.

(a) Suppose that Theory Pig starts at position (0, 0). At any time, he can step north (incrementing the first coordinate) or step east (incrementing the second coordinate). In how many different ways can he reach position (n, n), where n is a non-negative integer?

Theory Pig must take 2n steps in total. Of these, he must choose a subset of N to be north steps. This gives \binom{2n}{n} different ways to reach (n, n).

(b) How many different ways are there to list the numbers 1, 2, …, 2n such that the even numbers appear in increasing order and the odd numbers appear in decreasing order?

There are (2n)! ways to list the numbers 1, 2, …, n. We can define a n!-to-1 mapping that takes an arbitrary listing to a listing in which the even numbers are sorted in increasing order and the odd numbers remain as before. Thus, by the quotient rule there are (2n)!/n! listings in which the even numbers appear in increasing order. Similarly, we can define an n!-to-1 mapping that takes a listing in which the even numbers appear in increasing order and the odd numbers are in an arbitrary order to a listing in which the even numbers appear in increasing order (as before) and the odd numbers appear in decreasing order. Therefore, there are

\frac{(2n)!}{n! n!} = \binom{2n}{n}

listings in which the even numbers are increasing and the odd numbers are decreasing.

(c) Describe a bijection that maps each one of Theory Pig’s paths to a listing of the numbers 1, 2, … 2n with even numbers increasing and odd numbers decreasing.

Each time Theory Pig take a step north, write down an even number, starting with 2 and working up. Each time Theory Pig takes a step east, write an odd number, starting with 2n − 1 and working down.

Problem 3. (20 points) Suppose that every two people either know one another or else are strangers. How many people must there be in a room to guarantee that there are either 6 people who all know each other or 6 people who are all strangers to one another?

The solution to this problem is a number called R(6, 6). The solution to the simpler problem involving groups of only 5 people is called R(5, 5). Earlier in the course, we solved a stillsimpler version of this problem involving groups of just 3 people in about ten minutes. Finding R(5, 5) and R(6, 6) is a bit more tricky. The following is taken from a well-known text, Ten Lectures on the Probabilistic Method, by Joel Spencer:

Erdos [possibly the 20th century’s top mathematician] asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshall all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.

Given rumors that a new fleet is forming on Xoros 19, we had better take a stab at R(6, 6). For now, however, we will only try to prove that R(6, 6) > 17.

(a) If there are n people in a room, then how many different pairs of people are there?

\binom{n}{2}

(b) A configuration of a group of people is a setting of who-knows-who. For example, there are two possible configurations of a group of just two people: either they know each other or they are strangers. How many different configurations are possible in a room with n people?

Since every two people either know each other or are strangers, the number of configurations is

2^{\binom{n}{2}}.

(c) Suppose that there is a specific group of six people who all know each other. How many configurations are possible with this restriction?

2^{\binom{n}{2}−\binom{6}{2}}

(d) In a set of n people, how many different subsets of six people are there?

\binom{n}{6}

(e) Use your answers to the preceding two parts to find an upper bound on the number of configurations in which there exists some group of six people who all know each other.

There are \binom{n}{6} different sets of six people. For each set of six people, there are 2^{\binom{n}{2}−\binom{6}{2}} configurations in which these people all know each other. Therefore, there are at most

\binom{n}{6} · 2^{\binom{n}{2}−\binom{6}{2}}

configurations in which some set of six people all know each other.

(f) Give an upper bound on the number of configurations in which there exist either six people who all know each other or six people who are all strangers.

There are at most

\binom{n}{6} · 2^{\binom{n}{2}−\binom{6}{2}}

configurations in which some six people all know each other. By the same argument, there are at most this many configurations of six people that are all strangers. Therefore, there are at most

2 · \binom{n}{6} · 2^{\binom{n}{2}−\binom{6}{2}}

configurations in which some six people either all know each other or are all strangers.

(g) Use your answers to parts (b) and (f) to prove that there exists a configuration of 17 people such that no set of six people all know each other or are all strangers. This implies that R(6, 6) > 17.

By part (a), there are

2^{\binom{17}{2}}

configurations of 17 people. By part (f) there are at most

2 · \binom{17}{6} · 2^{\binom{17}{2}−\binom{6}{2}}

configurations in which some set of six people either all know each other or are all strangers. If the first quantity is greater than the second, then there must exist a configuration of 17 people such that there is no set of six people that all know each other or are all strangers. The second quantity divided by the first is

2 · \binom{17}{6} · 2^{−\binom{6}{2}} ≈ 0.75.  (1)

Therefore, the first quantity is greater than the second, as desired. The best known bounds are 102 ≤ R(6, 6) ≤ 165. Asymptotically, the simple technique outlined above gives a lower bound on R(k, k) that is within a factor of 2 of the best known.

Problem 4. (10 points) Find generating functions for the following sequences.

(a) < 0, 0, 1, 1, 1, 1, 1, … >

x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + … = x^{2} · (1 + x + x^{2} + x^{3} + x^{4} + …)
= \frac{x^{2}}{1 − x}

(b) < 0, 2, 4, 6, 8, 10, … >

0 + 2x + 4x^{2} + 6x^{3} + 8x^{4} + … = 2x · (0 + 1 + 2x + 3x^{2} + 4x^{3} …)
= 2x · \frac{d}{dx} (1 + x + x^{2} + x^{3} + x^{4} + …)
= 2x · \frac{d}{dx} (\frac{1}{1 − x})
= \frac{2x}{(1 − x)^{2}}

(c) < 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, … >

1 + x^{3} + x^{6} + x^{9} + x^{12} + … = \frac{1}{1 − x^{3}}

(d) < 2^{0}, 2^{1}, 2^{2}, 2^{3}, 2^{4}, 2^{5}, … >

2^{0} + 2^{1}x + 2^{2}x^{2} + 2^{3}x^{3} + 2^{4}x^{4} + …

= (2x)^{0} + (2x)^{1} + (2x)^{2} + (2x)^{3} + (2x)^{4} + …
= \frac{1}{1 − 2x}

(e) < −1, 0, 1, −1, 0, 1, −1, 0, 1, −1, 0, 1, … >

−1 + x^{2} − x^{3} + x^{5} − x^{6} + x^{8} − …

= (x^{2} + x^{5} + x^{8} + …) − (1 + x^{3} + x^{6} + …)
= x^{2}(1 + x^{3} + x^{6} + …) − (1 + x^{3} + x^{6} + …)
= (x^{2} − 1) · (1 + x^{3} + x^{6} + …)
= \frac{x^{2} − 1}{1 − x^{3}}

Problem 5. (10 points) Suppose that f(x) is the generating function for the sequence a_{0}, a_{1}, a_{2}, . . .. Find generating functions for the following sequences.

(a) < 0, 0, 0, a_{0}, a_{1}, a_{2}, … >

a_{0}x^{3} + a_{1}x^{4} + a_{2}x^{5} + … = x^{3} · (a_{0} + a_{1}x + a_{2}x^{2} + …)
= x^{3}f(x)

(b) < a_{0}, a_{1} + 1, a_{2} + 2, a_{3} + 3, … >

a_{0} + (a_{1} + 1)x + (a_{2} + 2)x^{2} + (a_{3} + 3)x^{3} + …

= (a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + …) + (0 + 1x + 2x^{2} + 3x^{3} + …)
= f(x) + \frac{x}{(1 − x)^{2}}

(c) < a_{0}, 0, a_{1}, 0, a_{2}, 0, a_{3}, 0, … >

a_{0} + a_{1}x^{2} + a_{2}x^{4} + a_{3}x^{6} + … = f(x^{2})

(d) < a_{0}, −a_{1}, a_{2}, −a_{3}, a_{4}, … >

a_{0} − a_{1}x + a_{2}x^{2} − a_{3}x^{3} + a_{4}x^{4} − … = f(−x)

(e) < a_{0}, 0, a_{2}, 0, a_{4}, 0, … >

a_{0} + a_{2}x^{2} + a_{4}x^{4} + a^{6}x^{6} + …
= \frac{1}{2}((a_{0} − a_{1}x + a_{2}x^{2} − a_{3}x^{3} + …)
+ (a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + …))
= \frac{1}{2}(f(−x) + f(x))

Problem 6. (10 points) For each of the following generating functions, find a closed-form expression for the coefficient of x^{n}.

(a)

\frac{5 − 11x}{4x^{2} − 5x + 1}

We will use the partial fractions method. The roots of the denominator are x = 1 and x = \frac{1}{4}. Therefore, we look for a partial fractions expansion of the form

\frac{5 − 11x}{(1 − x)(1 − 4x)} = \frac{A}{1 − x} + \frac{B}{1 − 4x}.

Multiplying by the denominators gives:

5 − 11x = A(1 − 4x) + B(1 − x)

Setting x = 1 gives A = 2, and setting x = \frac{1}{4} gives B = 3. Therefore, we can rewrite the generation function as

\frac{5 − 11x}{4x^{2} − 5x + 1} = \frac{2}{1 − x} + \frac{3}{1 − 4x}
= 2(1 + x + x^{2} + x^{3} + …) +
3(1 + 4x + 4^{2}x^{2} + 4^{3}x^{3} + …)

Therefore, the coefficient of x^{n} is 3 · 4^{n} + 2. (b)

\frac{2x}{(1 − x)^{3}}

The partial fractions expansion of the above expression is itself. Therefore, we take successive derivatives. One helpful observation is that the sequence generated by this function is equivalent to doubling and shifting the sequence generated by f(x) = 1/(1 − x)^{3}. Therefore, we only need to find the sequence generated by f(x), which involves easier derivatives.

f(x) = \frac{1}{(1 − x)^{3}}
f′(x) = \frac{3}{(1 − x)^{4}}
f′′(x) = \frac{3 · 4}{(1 − x)^{5}}
f′′′(x) = \frac{3 · 4 · 5}{(1 − x)^{6}}
. . . . . . . . .

f^{(n)}(x) = \frac{(n + 2)!}{2} · \frac{1}{(1 − x)^{n+3}}

The coefficient of x^{n} in f(x) is equal to f^{(n)}(0)/n!, which is (n + 1)(n + 2)/2. Therefore, the coefficient of x^{n} in the original generating function is n(n + 1).

Problem 7. (15 points) In this problem, we use generating functions to compute the number of m bit strings with a multiple of three 1’s. For example, if m = 4, then there are five such strings:

0000  1110  1101 1011  0111

(a) Use summation notation and binomial coefficients to describe the number of m-bit strings with a multiple of three 1’s.

\begin{matrix}⌊ & \frac{m}{3} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{m}{3i}

The following fact will be useful in evaluating this sum. Let z_{1} = 1, z_{2} = −\frac{1}{2} + \frac{\sqrt{3}}{2}i, and z_{3} = −\frac{1}{2} − \frac{\sqrt{3}}{2}i. The expression \frac{1}{3}(z_{1}^{k} + z_{2}^{k} + z_{3}^{k}) is then equal to 1 if k is a multiple of 3 and is equal to 0 otherwise.

(b) Left f(x) be a generating function for the series < a_{0}, a_{1}, a_{2}, … >. Give a closedform expression for the following sum.

∑_{i=0}^{∞} a_{3i}

∑_{i=0}^{∞} a_{3i} = ∑_{k=0}^{∞} a_{k} · \frac{z_{1}^{k} + z_{2}^{k} + z_{3}^{k}}{3}

= \frac{1}{3} · (∑_{k=0}^{∞} a_{k}z_{1}^{k} + ∑_{k=0}^{∞} a_{k}z_{2}^{k} + ∑_{k=0}^{∞} a_{k}z_{3}^{k})

= \frac{f(z_{1}) + f(z_{2}) + f(z_{3})}{3}

(c) Recall that f(x) = (1 + x)^{m} is the generating function for binomial coefficients; that is, for 0 ≤ k ≤ m, the coefficient of x^{k} is \binom{m}{k}, and for k > m, the coefficient of x^{k} is zero. Combine this fact and the two preceding problem parts to obtain a closed-form expression for the number of m-bit strings with a multiple of three 1’s.

\begin{matrix}⌊ & \frac{m}{3} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{m}{3i} = \frac{1}{3}((1 + z_{1})^{m} + (1 + z_{2})^{m} + (1 + z_{3})^{m})

= \frac{1}{3} (2^{m} + (\frac{1}{2} + \frac{\sqrt{3}}{2}i)^{m} + (\frac{1}{2} − \frac{\sqrt{3}}{2}i)^{m})

(d) Use DeMoivre’s formula, restated below, to eliminate complex numbers from your solution.

(cos θ + i sin θ)^{n} = cos(nθ) + i sin(nθ)

\frac{1}{3} (2^{m} + (\frac{1}{2} + \frac{\sqrt{3}}{2}i)^{m} + (\frac{1}{2} − \frac{\sqrt{3}}{2}i)^{m})
= \frac{1}{3} (2^{m} + (cos \frac{π}{3} + i sin \frac{π}{3} )^{m} + (cos \frac{π}{3} − i sin \frac{π}{3} )^{m})
= \frac{1}{3} (2^{m} + cos \frac{mπ}{3} + i sin \frac{mπ}{3} + cos \frac{mπ}{3} − i sin \frac{mπ}{3} )
= \frac{1}{3} (2^{m} + 2 cos \frac{mπ}{3} )

For example, the number of 4-bit strings with a multiple of three ones is equal to

\frac{1}{3} (2^{4} + 2 cos \frac{4π}{3} ) = \frac{1}{3} (16 + 2 · (−\frac{1}{2}))
= 5

Problem 8. (20 points) A string of parentheses is called “balanced” if the number of (’s is equal to the number of )’s and the number of )’s never exeeds the number of (’s as the string is read from left to right. For example, (()())((())) is a balanced string, but ())( is not. With three pairs of parentheses, five different balanced strings can be formed. These five strings are listed below.

((())) (()()) (())() ()(()) ()()()

In general, the number of balanced strings increases rapidly with the number of pairs of parentheses. Your diligent TA stayed up until dawn, slaving away with a dull pencil stub, working out the following table:^{1}

Pairs of Parentheses  Number of Balanced Strings
0  1
1  1
2  2
3  5
4  14
5  42
6  132
7  429
8  1430
9  4862
10  16796
11  58786
12  208012

In an apparently unrelated calculation, your exhausted TA then used his final drops of energy and the last nubbin of his pencil to evaluate 500000−1000\sqrt{249999} out to 72 decimal places:^{2}

1.000001000002000005000014000042000132000429001430004862016796058786208012 …

Compare the table to the irrational number. The goal of this problem is to explain the apparently miraculous correspondence.

(a) Let p_{n} be the number of balanced strings containing n pairs of parentheses. Express p_{n} with a recurrence equation and sufficient base cases.

Note that every balanced string with n ≥ 1 pairs of parentheses consists of a balanced string with k pairs, all enclosed in parentheses, followed by a balanced string with n − k − 1 pairs:

1This is a lie; he cranked it out with a C program in about six minutes.

2This is also a lie; he plugged the thing into Maple.

string with n pairs = ( string with k pairs ) string with n − k − 1 pairs

This observation suggests the following recurrence equation:

p_{0} = 1
p_{n} = ∑_{k=0}^{n−1} p_{k} · p_{n−k−1} (n ≥ 1)

(b) Let P (x) be the generating function for the number of balanced strings; that is,

P (x) = p_{0} + p_{1}x + p_{2}x^{2} + p_{3}x^{3} + ….

Using the recurrence relation as a guide, find a (non-trivial) equation relating and P (x) and the square of P (x).

The summation in the recurrence equation suggests

P (x) = xP (x)^{2} + 1.

We can verify this equation using the recurrence relation.

xP (x)^{2} + 1 = x(p_{0} + p_{1}x + p_{2}x^{2} + p_{3}x^{3} + …)^{2} + 1
= x(p_{0}^{2} + (p_{0}p_{1} + p_{1}p_{0})x + (p_{0}p_{2} + p_{1}p_{1} + p_{2}p_{0})x^{2} + …) + 1
= 1 + p_{0}^{2}x + (p_{0}p_{1} + p_{1}p_{0})x^{2} + (p_{0}p_{2} + p_{1}p_{1} + p_{2}p_{0})x^{3} + …
= 1 + p_{1}x + p_{2}x^{2} + p_{3}x^{3} + …
= P (x)

(c) Apply the quadratic formula to obtain a closed-form expression for the generating function P (x).

Given that P (x) = xP (x)^{2} + 1, the quadratic formula implies that

P (x) = \frac{1 ± \sqrt{1 − 4x}}{2x}.

If x is small, then P (x) should be about p_{0} = 1. Therefore, the correct choice of sign is

P (x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

(d) Show that P (1/1000000) = 500000 − 1000\sqrt{249999}.

P (1/1000000) = \frac{1 − \sqrt{1 − \frac{4}{1000000}}}{(\frac{2}{1000000})}

= 500000 − 500000\sqrt{\frac{249999}{250000}}
= 500000 − 1000\sqrt{249999}

(e) Explain why the digits of this irrational number encode the number of balanced strings of parentheses.

Suppose that we symbolically carry out the substitution done in the preceding problem part.

P (x) = p_{0} + p_{1}x + p_{2}x^{2} + p_{3}x^{3} + …
P (10^{−6}) = p_{0} + p_{1}10^{−6} + p_{2}10^{−12} + p_{3}10^{−18} + …

Thus, p_{0} appears in the units position, p_{1} appears in the millionths position, p_{2} appears in the trillionths position, and so forth.