COMBINATORICS. MIDTERM TEST. SOLUTIONS
1. Basics and GF’s Problem 1. Find [x3n ]e2x (the coefficient by x3n in the power series expansion of e2x ). Solution 1. Since e
2x
=
∞ X 2k xk k=0
k!
,
we have
23n . (3n)!
[x3n ]e2x = {take k = 3n above} = Problem 2. Show that
n n n k n n n +2 +4 + ...2 + ··· + 2 = 3n . (1) 0 1 2 k n n X k n n x Solution 2. Take the binomial theorem (1 + x) = , and set x = 2. See also Problem 11 below. k k=0 Problem 3. What is the total number of ways in which the letters in the word “PETERSBURG” can be rearranged? 10! Solution 3. The answer is . If all letters were distinct (“PE1 TE2 R1 SBUR2 G”), it would be 10! 2! · 2! rearrangements, but to any rearrangement of distinct letters correspond 2!·2! rearrangements of the original letters, because we can interchange E1 with E2 , as well as R1 with R2 . Problem 4. Solve the recurrence (using generating functions): an+2 = 3an+1 + 4an − 6n − 1 (n ≥ 0),
a1 = 4,
a0 = 2.
(Advice: substitute your answer into the equation to check yourself.) Solution 4. Multiply both sides of the recurrence relation by xn+2 and sum over all n ≥ 0 (the range where the relation holds): ∞ X
an+2 x
n+2
= 3x
n=0
Let f (x) = ∞ X
P∞
n=0
∞ X
an+1 x
n+1
+ 4x
n=0
2
∞ X
n
an x − 6
n=0
∞ X
nx
n+2
n=0
−
∞ X
xn+2 .
n=0
n
an x be the generating function of an ’s, we have
an+2 xn+2 = f (x)−a0 −a1 x = f (x)−2−4x,
n=0
∞ X
an+1 xn+1 = f (x)−a0 = f (x)−2,
n=0
n=0
Moreover, we have ∞ X n=0
n+2
nx
x3 , = (1 − x)2
∞ X
xn+2 =
n=0
x2 . 1−x
Thus, we get the following equation on f (x): f (x) − 2 − 4x = 3xf (x) − 6x + 4x2 f (x) − 1
∞ X
6x3 x2 − , (1 − x)2 1 − x
an xn = f (x).
2
COMBINATORICS. MIDTERM TEST. SOLUTIONS
which gives 2 − 6x + 5x2 − 7x3 (1 − x)2 (1 − 3x − 4x2 ) Expressing f (x) as a sum of partial fractions gives 1 1 1 1 f (x) = + + . − 2 (1 − x) 1 − x 1 + x 1 − 4x This immediately gives the answer: ∞ ∞ ∞ ∞ X X X X n n n n f (x) = (n + 1)x − x + (−1) x + 4n xn , f (x) =
n=0
n=0
n=0
n=0
so an = n + (−1)n + 4n . Problem 5. Compute the sum:
∞ X 10n + 3n n=1
Solution 5. We have ∞ X 10n + 3n n=1
n!
=
∞ X 10n n=1
n!
+3
n! ∞ X n=1
(Advice: note the range of summation.)
1 = (n − 1)!
∞ X 10n n=0
n!
! −1
∞ X 1 +3 = e10 − 1 + 3e. n! n=0
2. Catalan Numbers Of these two problems, solve at least one (of your choice) Problem 6. Show that the number of Young diagrams which are inside the staircase shaped Young diagram (n − 1, n − 2, . . . , 1) is Catalann . (Hint: bijection with certain up-right paths.) ∅ Solution 6. Bijection with up-right paths on the lattice starting at (0, 0) and ending at (n, n) which never go below the diagonal — the part of the n × n square which is above such paths is a Young diagram:
Problem 7. Show that the number of tiling of the staircase shape (n, n−1, n−2, . . . , 2, 1) with n rectangles is Catalann . (Hint: derive the Catalan recurrence relation by deleting one of the tiling rectangles.)
Solution 7. Deleting the upper left rectangle leads to two tilings of smaller staircase Young diagrams, which gives the desired recurrence. Indeed, let the upper left rectangle be K × L. It is readily seen that K + L = n + 1, and deleting this rectangle we get a pair of independent tilings of the staircase shapes (K − 1, K − 2, . . . , 2, 1) and (L − 1, L − 2, . . . , 2, 1). Thus, we get our recurrence for the unknown number of tilings: n n−1 X X X Cn = CK−1 CL−1 = CK−1 Cn−K = CK Cn−K−1 , K,L : K+L=n+1
K=1
K=0
which is the Catalan recurrence. Noting that C0 = C1 = 1, we conclude the proof.
COMBINATORICS. MIDTERM TEST. SOLUTIONS
3
3. Lagrange inversion Problem 8. Write a solution to the cubic equation x − 1 = ax3 , that is, find the generating series x = x(a). Solution 8. Set y = x − 1, then we have the equation y = a(y + 1)3 , and by Lagrange inversion, y(a) = y1 a + y2 a2 + y3 a3 + . . . , and 1 n−1 1 3n 3n yn = [u ](y − 1) = , n n n−1 so
∞ X 1 3n an , y(a) = n n − 1 n=1
and the answer is
∞ X 1 3n x(a) = 1 + an . n n−1 n=1 4. Asymptotics
Problem 9. Let an be a sequence with the generating function ∞ X
2 . (1 − x)(1 − 2x)(1 − 3x) n=0 P n (a) What is the radius of convergence of the series ∞ n=0 an x ? (Hint: use singular points.) (b) Find minimal possible R such that an grows slower than ( R1 + )n for any > 0. (c) Expand f (x) as a sum of partial fractions. Find an explicit formula for an . f (x) :=
an x n =
Solution 9. (a) The singular points are, clearly, x = 1, x = 1/2 and x = 1/3. So the closest one is x = 1/3, and the radius of convergence is the distance to this closest point, it is R = 13 . (b) The same R = 13 serves here, so an grows slower than (3 + )n for any > 0. (c) The expansion of f (x) is ∞ h i X 8 9 1 1 − 8 · 2n + 9 · 3n xn . − + = f (x) = 1 − x 1 − 2x 1 − 3x n=0 so an = 1 − 8 · 2n + 9 · 3n . Problem 10. Let an = 4n . 2n (a) Make sure that the sequence an is hypergeometric. Deduce hypergeometric-type asymptotics for the sequence an . (b) Using Stirling’s formula, find exact asymptotics of the sequence an . Solution 10. First, we write asymptotics of bk = 2k , and then substitute k = 2n everywhere. k (a) We have 2k+2 k 2 + 23 k + 12 bk+1 (2k + 2)(2k + 1) = k+1 = = 4 , 2k bk (k + 1)2 k 2 + 2k + 1 k 1
1
so we have bk ∼ Const · 4k · k − 2 , and thus an ∼ Const0 · 42n · n− 2 (with some other constant). (b) Using Stirling’s formula, r √ 2k (2k)! 2π · 2k (2k/e)2k 1 √ ∼ =√ = · 22k , 2k k k!k! (k/e) πk 2π · k 2π · k
4
COMBINATORICS. MIDTERM TEST. SOLUTIONS
and thus
r an ∼
1 · 24n . 2πn
5. Supplementary Problems Problem 11. Give a combinatorial proof of (1) in Problem 2. (Hint: interpret 3n as the number of all sequences of length n with letters a, b, c.) Solution 11. On the right we have 3n , which is the number of all sequences of length n with letters a, b, c. Any such sequence has, say, n − k letters a, and k remaining letters are b or c. Forn any k = 0, 1, . . . , n, the number of ways to choose such a sequence with k letters a is 2k nk : here nk = n−k means the number of k ways to choose n − k positions to place a’s, and 2 is the number of words of length k with letters b, c. Problem 12. Solve the differential equation using generating functions: f 0 (x) + xf (x) = 0. (Advice: substitute your answer into the equation to check yourself.) P n Solution 12. Let f (x) = ∞ n=0 an x , then we get the equation ∞ ∞ X X nan xn−1 + an xn+1 = 0, n=0
or, equivalently, a1 +
∞ h X
n=0
i (n + 1)an+1 + an−1 xn = 0,
n=1
which means that (we compare the coefficients by 1, x, x2 , x3 , . . . ): a0 a2 a0 a4 a0 a1 = 0, a2 = − , a3 = 0, a4 = − = , a5 = 0, a6 = − = − , 2 4 8 6 48 We see that the odd coefficients an are zero, and for the even coefficients we have a2k−2 , a2k = − 2k which readily implies that (−1)k 2−k a2k = a0 . k! It remains to sum the power series: ∞ X x2 (−1)k 2−k 2k x = a0 e − 2 . f (x) = a0 k! k=0
...
Problem 13. Show that any minor (= determinant formed by some of the rows i1 , . . . , ik and the same number of columns j1 , . . . , jk , k is arbitrary) of the matrix 1 α α2 . . . αN −1 αN 0 1 α . . . αN −2 αN −1 ........................... 0 0 0 ... 1 α 0 0 0 ... 0 1 is nonnegative (here α > 0). (Hint: use nonintersecting paths approach.) Solution 13. Draw a graph, and observe that any minor corresponds to a choice of entrances/exits. So its determinant is nonnegative because it is (by KMGLGV) the “number” of collections of nonintersecting paths (i.e., every path is counted with its weight; the weight of a collection = product of weights of paths).
