3.E: Generating Functions (Exercises)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
3.1: Newton's Binomial Theorem
For some of these exercises, you may want to use the sage applet above, in example 3.1.4, or your favorite computer algebra system.
Ex 3.1.1 Prove that \({r\choose k}={r1\choose k1}+{r1\choose k}\).
Ex 3.1.2 Show that the Maclaurin series for \((x+1)^r\) is \(\sum_{i=0}^\infty {r\choose i}x^i\).
Ex 3.1.3 Concerning example 3.1.4, show that all coefficients beginning with \(x^{16}\) are 180.
Ex 3.1.4 Use a generating function to find the number of solutions to \(\ds x_1+x_2+x_3+x_4=14\), where \(0\le x_1\le3\), \(2\le x_2\le5\), \(0\le x_3\le5\), \(4\le x_4\le6\).
Ex 3.1.5 Find the generating function for the number of solutions to \(\ds x_1+x_2+x_3+x_4=k\), where \(0\le x_1\le\infty\), \(3\le x_2\le\infty\), \(2\le x_3\le5\), \(1\le x_4\le5\).
Ex 3.1.6 Find a generating function for the number of nonnegative integer solutions to \(3x+2y+7z=n\).
Ex 3.1.7 Suppose we have a large supply of red, white, and blue balloons. How many different bunches of 10 balloons are there, if each bunch must have at least one balloon of each color and the number of white balls must be even?
Ex 3.1.8 Use generating functions to show that every positive integer can be written in exactly one way as a sum of distinct powers of 2.
Ex 3.1.9 Suppose we have a large supply of blue and green candles, and one gold candle. How many collections of \(n\) candles are there in which the number of blue candles is even, the number of green candles is any number, and the number of gold candles is at most one?
3.2: Exponential Generating Functions
Ex 3.2.1 Find the coefficient of \(x^9/9!\) in the function of example 3.2.1. You may use Sage or a similar program.
Ex 3.2.2 Find an exponential generating function for the number of permutations with repetition of length \(n\) of the set \(\{a,b,c\}\), in which there are an odd number of \(a\,\)s, an even number of \(b\,\)s, and an even number of \(c\,\)s.
Ex 3.2.3 Find an exponential generating function for the number of permutations with repetition of length \(n\) of the set \(\{a,b,c\}\), in which the number of \(a\,\)s is even and at least 2, the number of \(b\,\)s is even and at most 6, and the number of \(c\,\)s is at least 3.
Ex 3.2.4 In how many ways can we paint the 10 rooms of a hotel if at most three can be painted red, at most 2 painted green, at most 1 painted white, and any number can be painted blue or orange?
Ex 3.2.5 Recall from section 1.4 that the Bell numbers \(B_n\) count all of the partitions of \(\{1,2,\ldots,n\}\).
Let \(\ds f(x)=\sum_{n=0}^\infty B_n\cdot {x^n\over n!}\), and note that \(\) f'(x)=\sum_{n=1}^\infty B_n {x^{n1}\over (n1)!}= \sum_{n=0}^\infty B_{n+1}{x^{n}\over n!}= \sum_{n=0}^\infty \left(\sum_{k=0}^n {n\choose k}B_{nk}\right) {x^{n}\over n!}, \(\) using the recurrence relation 1.4.1 for \(B_{n+1}\) from section 1.4. Now it is possible to write this as a product of two infinite series: \(\) f'(x) = \left(\sum_{n=0}^\infty B_n\cdot {x^n\over n!}\right) \left(\sum_{n=0}^\infty a_n x^n\right) = f(x)g(x). \(\) Find an expression for \(a_n\) that makes this true, which will tell you what \(g(x)\) is, then solve the differential equation for \(f(x)\), the exponential generating function for the Bell numbers. From section 1.4, the first few Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437. You can check your answer in Sage.
3.3: Partitions of Integers
Ex 3.3.1 Use generating functions to find \(p_{15}\).
Ex 3.3.2 Find the generating function for the number of partitions of an integer into distinct odd parts. Find the number of such partitions of 20.
Ex 3.3.3 Find the generating function for the number of partitions of an integer into distinct even parts. Find the number of such partitions of 30.
Ex 3.3.4 Find the number of partitions of 25 into odd parts.
Ex 3.3.5 Find the generating function for the number of partitions of an integer into \(k\) parts; that is, the coefficient of \(x^n\) is the number of partitions of \(n\) into \(k\) parts.
Ex 3.3.6 Complete row 8 of the table for the \(p_k(n)\), and verify that the row sum is 22, as we saw in example 3.3.3.
Ex 3.3.7 A partition of \(n\) is selfconjugate if its Ferrers diagram is symmetric around the main diagonal, so that its conjugate is itself. Show that the number of selfconjugate partitions of \(n\) is equal to the number of partitions of \(n\) into distinct odd parts.
3.4: Recurrence Relations
Ex 3.4.1 Find the generating function for the solutions to \(h_n=4h_{n1}3h_{n2}\), \(h_0=2\), \(h_1=5\), and use it to find a formula for \(h_n\).
Ex 3.4.2 Find the generating function for the solutions to \(h_n=3h_{n1}+4h_{n2}\), \(h_0=h_1=1\), and use it to find a formula for \(h_n\).
Ex 3.4.3 Find the generating function for the solutions to \(h_n=2h_{n1}+3^n\), \(h_0=0\), and use it to find a formula for \(h_n\).
Ex 3.4.4 Find the generating function for the solutions to \(h_n=4h_{n2}\), \(h_0=0\), \(h_1=1\), and use it to find a formula for \(h_n\). (It is easy to discover this formula directly; the point here is to see that the generating function approach gives the correct answer.)
Ex 3.4.5 Find the generating function for the solutions to \(h_n=h_{n1}+h_{n2}\), \(h_0=1\), \(h_1=3\), and use it to find a formula for \(h_n\).
Ex 3.4.6 Find the generating function for the solutions to \(h_n=9h_{n1}26h_{n2}+24h_{n3}\), \(h_0=0\), \(h_1=1\), \(h_2=1\), and use it to find a formula for \(h_n\).
Ex 3.4.7 Find the generating function for the solutions to \(h_n=3h_{n1}+4h_{n2}\), \(h_0=0\), \(h_1=1\), and use it to find a formula for \(h_n\).
Ex 3.4.8 Find a recursion for the number of ways to place flags on an \(n\) foot pole, where we have red flags that are 2 feet high, blue flags that are 1 foot high, and yellow flags that are 1 foot high; the heights of the flags must add up to \(n\). Solve the recursion.
Ex 3.4.9 In Fibonacci's original problem, a farmer started with one (newborn) pair of rabbits at month 0. After each pair of rabbits was one month old, they produced another pair each month in perpetuity. Thus, after 1 month, he had the original pair, after two months 2 pairs, three months, 3 pairs, four months, 5 pairs, etc. The number of pairs of rabbits satisfies \(h_n=h_{n1}+h_{n2}\), \(h_0=h_1=1\). (Note that this is slightly different than our definition, in which \(h_0=0\).)
Suppose instead that each mature pair gives birth to two pairs of rabbits. The sequence for the number of pairs of rabbits now starts out \(h_0=1\), \(h_1=1\), \(h_2=3\), \(h_3=5\), \(h_4=11\). Set up and solve a recurrence relation for the number of pairs of rabbits. Show also that the sequence statisfies \(h_n=2h_{n1}+(1)^n\).
3.5: Catalan Numbers
Ex 3.5.1 Show that \(\) {2n\choose n}{2n\choose n+1}={1\over n+1}{2n\choose n}. \(\)
Ex 3.5.2 Find a simple expression \(f(n)\) so that \(C_{n+1}=f(n)C_n\). Use this to compute \(C_1,\ldots,C_6\) from \(C_0\).
Ex 3.5.3 Show that if \(A_n\) is the number of properly matched sequences of parentheses of length \(2n\), then \(\) A_n=\sum_{i=0}^{n1} A_iA_{ni1}. \(\) Do this in the same style that we used for the number of rooted binary trees: Given all the sequences of shorter length, explain how to combine them to produce the sequences of length \(2n\), in such a way that the sum clearly counts the number of sequences. Hint: Prove the following lemma: If \(s\) is a properly matched sequence of parentheses of length \(2n\), \(s\) may be written uniquely in the form \((s_1)s_2\), where \(s_1\) and \(s_2\) are properly matched sequences of parentheses whose lengths add to \(2n2\). For example, \((())()= ([()])[()]\) and \(()(())=([\,])[(())]\), with the sequences \(s_1\) and \(s_2\) indicated by \([\,]\). Note that \(s_1\) and \(s_2\) are allowed to be empty sequences, with length 0.
Ex 3.5.4 Consider a "staircase'' as shown below. A path from \(A\) to \(B\) consists of a sequence of edges starting at \(A\), ending at \(B\), and proceeding only up or right; all paths are of length 6. One such path is indicated by arrows. The staircase shown is a "\)3 \times 3\)'' staircase. How many paths are there in an \(n\times n\) staircase?
Ex 3.5.5 A convex polygon with \(n\ge3\) sides can be divided into triangles by inserting \(n3\) nonintersecting diagonals. In how many different ways can this be done? The possibilities for \(n=5\) are shown.





Ex 3.5.6 A partition of a set \(S\) is a collection of nonempty subsets \(A_i\subseteq S\), \(1\le i\le k\) (the parts of the partition), such that \(\bigcup_{i=1}^k A_i=S\) and for every \(i\not=j\), \(A_i\cap A_j=\emptyset\). For example, one partition of \(\{1,2,3,4,5\}\) is \(\{\{1,3\}\), \(\{4\}\), \(\{2,5\}\}\).
Suppose the integers \(1,2,\ldots,n\) are arranged on a circle, in order around the circle. A partition of \(\{1,2,\ldots,n\}\) is a noncrossing partition if it satisfies this additional property: If \(w\) and \(x\) are in some part \(A_i\), and \(y\) and \(z\) are in a different part \(A_j\), then the line joining \(w\) to \(x\) does not cross the line joining \(y\) to \(z\). The partition above, \(\{1,3\}\), \(\{4\}\), \(\{2,5\}\), is not a noncrossing partition, as the the line 1–3 crosses the line 2–5.
Find the number of noncrossing partitions of \(\{1,2,\ldots,n\}\).
Recall from section 1.4 that the Bell numbers count all of the partitions of \(\{1,2,\ldots,n\}\). Hence, this exercise gives us a lower bound on the total number of partitions.
Ex 3.5.7 Consider a set of \(2n\) people sitting around a table. In how many ways can we arrange for each person to shake hands with another person at the table such that no two handshakes cross?