# Generating functions for compositions

Let $g(n)$ be the number of compositions of n where each part is an odd number. Let $h(n)$ number of compositions of $n$ where each part is either 1 or 2. Using the ordinary generating functions $G(x)$ and $H(x)$, show that $g(n) = h(n-1)$

• Hello! Please provide us with a bit of information about what you've tried and where you're getting stuck. Do that, and it will be much easier for us to figure out how to best help you. – Nick Peterson Apr 3 '14 at 11:26
• @NicholasR.Peterson I have no idea about this one :( Would appreciate anything to get me started. – Dave Apr 3 '14 at 12:32
• Can you write down the generating functions for the case when there are no restrictions on the compositions? – ShreevatsaR Apr 4 '14 at 4:05

Here are the steps which are quite simple.

We have by inspection that $$g_n = [z^n] \sum_{k=1}^n \left(\frac{z}{1-z^2}\right)^k$$ and that $$h_n = [z^n] \sum_{k=1}^n \left(z+z^2\right)^k.$$

Now observe that in both cases the terms being summed start at $z$ and hence their powers start at $k$. That means we can extend both sums to infinity without affecting the coefficient of $z^n$ to obtain

$$g_n = [z^n] \sum_{k=1}^\infty \left(\frac{z}{1-z^2}\right)^k$$ and that $$h_n = [z^n] \sum_{k=1}^\infty \left(z+z^2\right)^k.$$

These are both geometric series and we have $$G(z) = \frac{z}{1-z^2} \frac{1}{1-z/(1-z^2)} = \frac{z}{1-z^2-z}$$ and $$H(z) = (z+z^2) \frac{1}{1-(z+z^2)} = \frac{z+z^2}{1-z-z^2}$$ The conclusion is that $$G(z) = \frac{z}{1-z-z^2} \quad\text{and}\quad H(z) = \frac{z+z^2}{1-z-z^2}.$$

We recognise $G(z)$ as the generating function of the Fibonacci numbers so that $$g_n = F_n \quad\text{and}\quad h_n = F_n + F_{n-1} = F_{n+1}.$$ This concludes the proof that $g_n = h_{n-1}.$

• +1. But note that: (A) your generating function $\frac{z}{1-z-z^2}=z+z^2+2z^3+\dots$. But arguably it makes sense to say $g(0)=1$ (for the empty composition), which gives the GF $\frac{z}{1-z-z^2}+1=\frac{1-z^2}{1-z-z^2}$ as in my answer. Similarly, $\frac{z+z^2}{1-z-z^2}=z+2z^2+3z^3+\dots$, and adding $h(0)=1$ gives $\frac{z+z^2}{1-z-z^2}+1=\frac{1}{1-z-z^2}$. Allowing the zero values lets us say that $g(n)=h(n-1)$ for $n\ge1$ instead of only $n\ge2$. (B) We can argue directly from GFs instead of using facts about Fibonacci numbers: in your notation, we have $zH(z)=G(z)+z$, which proves it. – ShreevatsaR Apr 6 '14 at 5:57

Let $\mathcal{O}$ denote the class of all odd numbers, so that it has generating function $O(z) = z + z^3 + z^5 + \dots = \dfrac{z}{1-z^2}$. Then the class of compositions into odd parts is $$\mathcal{G} = \operatorname{S\scriptsize EQ}(\mathcal{O}) \implies G(z) = \frac{1}{1-O(z)} = \frac{1}{1-\frac{z}{1-z^2}} = \frac{1-z^2}{1-z-z^2}$$ where $G(z) = \sum_{n \ge 0} g(n) z^n$ is the generating function for $\mathcal{G}$.

Similarly, let $\mathcal{C}$ denote the class containing just the numbers $1$ and $2$ (so $C(z) = z+z^2$), then the class of compositions into parts equal to $1$ and $2$ is $$\mathcal{H} = \operatorname{S\scriptsize EQ}(\mathcal{C}) \implies H(z) = \frac{1}{1-C(z)} = \frac{1}{1-z-z^2}$$ where $H(z) = \sum_{n \ge 0} h(n) z^n$ is the generating function for $\mathcal{H}$.

Now you want to prove that $g(n) = h(n-1)$ for $n \ge 1$, or equivalently that $g(n+1) = h(n)$ for $n \ge 0$. We have $$\sum_{n \ge 0}g(n+1)z^n = \frac{G(z) - g(0)}{z} = \frac1z \left( \frac{1-z^2}{1-z-z^2} - 1\right) = \frac{1}{1-z-z^2} = H(z)$$ which proves the assertion.

• We can also prove $g(n) = h(n-1)$ for $n \ge 1$ by noticing that $$\sum_{n \ge 1}h(n-1)z^n = zH(z) = \frac{z}{1-z-z^2}=\frac{1-z^2-(1-z-z^2)}{1-z-z^2} = G(z) - 1 = \sum_{n\ge 1}g(n)z^n$$ – ShreevatsaR Apr 6 '14 at 6:03