# Solving combinatorial problems with symbolic method and generating functions

I am trying to solve the following problems:

a) Let $$\mathcal{F}$$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length. How can $$\mathcal{F}$$ be constructed with simpler objects? How does the generating function look like?

b) Show with generating functions: The number of partitions of n into different summands equals the number of partitions of n into odd summands.

c) Show with generating functions: The number of compositions of n into summands being 1 or 2 equals the number of compositions of n+2 into summands greater than or equal 2.

My solutions:

a) I have no idea here.

b) Let $$\mathcal{P}$$ be the partition in different summands. Then $$\mathcal{P} = (\{\epsilon\}+\{1\}) \times (\{\epsilon\}+\{2\})\times (\{\epsilon\}+\{3\})\times ...$$

$$\Rightarrow P(z) = (1+z)\cdot (1+z^2) \cdot (1+z^3) \cdot \dotsc = \frac{1}{(1-z)\cdot(1-z^3)\cdot(1-z^5)\cdot \dotsc}$$

Now let $$\tilde{\mathcal{P}}$$ be the partition in odd summands. Then $$\tilde{\mathcal{P}} = \{1\}^{\ast}\times\{3\}^{\ast}\times\{5\}^{\ast}\times\dotsc$$

$$\Rightarrow \tilde{P(z)} = \frac{1}{1-z}\cdot\frac{1}{1-z^3}\cdot\frac{1}{1-z^5}\cdot \dotsc$$.

Therefore $$P(z) = \tilde{P}(z)$$ and so $$[z^n]P(z) = [z^n]\tilde{P}(z)$$, which proofs that the numbers of partitions of n are the same.

c) Let $$\mathcal{K}$$ be the number of compositions of n into 1s and 2s. Then $$\mathcal{K} = \{1,2\}^{\ast}$$ and so $$K(z) = \frac{1}{1-(z+z^2)}$$.

Let $$\tilde{\mathcal{K}}$$ be the number of compositions of n+2 into 2,3,4,5,6,7,... Then $$\tilde{\mathcal{K}} = \{2,3,4,5,6,...\}^{\ast}$$ and therefore $$\tilde{K}(z) = \frac{1}{1-(z^2+z^3+z^4+z^5+...)}$$.

I am not sure if I have determined $$\mathcal{K}, \tilde{\mathcal{K}}, K(z)$$ and $$\tilde{K}(z)$$ correctly and if so, I don't know how to show that $$[z^n]K(z) = [z^{n+2}]\tilde{K}(z)$$.

So I'd very much appreciate your help on a) and c). Thanks in advance!

• I am confused about (c). There are two compositions of $2$ into ones and twos: $1+1$ and $2$. There is only one composition of $4$ into threes or more: $4$. – Mike Earnest Mar 21 at 18:25
• @MikeEarnest Thanks for your comment, you are right, I made a mistake. It should say "greater than OR EQUAL 2". I will correct it, sorry! – Studentu Mar 21 at 18:28

Saying that there are no adjacent ones is almost equivalent to saying that every $$1$$ is followed by a $$0$$. In that case, the string is freely built out of copies of $$0$$ and $$10$$, so this is $$\{0,10\}^*$$. However, there is also optionally a $$1$$ at the end which is not followed by a zero, so it is more like $$\{0,10\}^*\times \{\varepsilon,1\}$$.

Let $$k_n$$ be the number of compositions of $$n$$ into $$\{2,3,4,\dots\}$$. What you found is $$\frac1{1-(z^2+z^3+\dots)}=\sum_{n=0}^\infty k_n x^n=\tilde K(z)$$ It is probability easier to find $$\sum_{n=0}^\infty k_{n+2} x^n=K_2(z)$$ Then, all you have to do is prove that $$K_2(z)=K(z)$$, which is simple algebra.

You are almost done! Can you see how to easily get $$K_2$$ from $$\tilde K$$?

Note $$K_2(z)=\sum_{n=0}^\infty k_{n+2}x^n=\sum_{n=2}^\infty k_nx^{n-2}=\frac1{x^2}\sum_{n=2}^\infty k_nx^n$$ The last summation almost looks like $$\tilde K(z)$$. The only problem is that the summation starts from $$n=2$$, not $$n=0$$. Therefore, the summation $$\sum_{n=2}^\infty k_nx^n$$ is attained from $$\tilde K(z)$$ by subtracting the first two terms.

• Thanks for your reply! I am going to try to solve it with the information you gave and let you know if it worked. :) – Studentu Mar 21 at 18:46
• @Studentu Sure! Just to clarify, $K'(z)$ does not refer to the derivative of $K(z)$, it is just a new function. – Mike Earnest Mar 21 at 18:54
• @Studentu See edit for more details. I changed $K'$ to $K_2$ to avoid confusion. – Mike Earnest Mar 21 at 19:10
• @Studentu Looks good! – Mike Earnest Mar 22 at 0:06
• @Studentu Very subtle error! You need to instead to instead subtract $\color{red}1\cdot 1+0\cdot z$ from $\tilde K$. Because of the empty composition, $k_0=1$. This now works. – Mike Earnest Mar 22 at 1:28

Your approach is fine. With $${\mathcal{K}} = \{1,2\}^{\ast}$$ we obtain \begin{align*} K(z) &= \frac{1}{1-\left(z+z^2\right)}\\ &=\frac{1}{1-z-z^2}\tag{1} \end{align*}

and with $$\tilde{\mathcal{K}} = \{2,3,4,5,6,...\}^{\ast}$$ we obtain \begin{align*} \tilde{K}(z) &= \frac{1}{1-(z^2+z^3+z^4+z^5+\cdots)}\\ &=\frac{1}{1-\frac{z^2}{1-z}}\tag{2}\\ &=\frac{1-z}{1-z-z^2}\\ &=1+\frac{z^2}{1-z-z^2}\tag{3} \end{align*}

Comment:

We obtain from (1) and (3) for $$n\geq 1$$

\begin{align*} \color{blue}{[z^{n+2}]\tilde{K}(z)} &=[z^{n+2}]\left(1+\frac{z^2}{1-z-z^2}\right)\\ &=[z^{n+2}]\frac{z^2}{1-z-z^2}\tag{4}\\ &=[z^n]\frac{1}{1-z-z^2}\tag{5}\\ &\,\,\color{blue}{=[z^n]K(z)} \end{align*}

and the claim follows.

Comment:

• In (4) we skip the term $$1$$ which does not contribute to the coefficient of $$z^{n+2}$$ since $$n\geq 1$$.

• In (5) we apply the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$.

Note the coefficients of \begin{align*} K(z)&=\frac{1}{1-z-z^2}\\ &=\color{blue}{1}+\color{blue}{1}z+\color{blue}{2}z^2+\color{blue}{3}z^3+\color{blue}{5}z^4+\color{blue}{8}z^5+\cdots \end{align*} are the Fibonacci numbers.

We start with binary sequences with no consecutive equal characters at all. See example III.24 Smirnov words from Analytic Combinatorics by P. Flajolet and R. Sedgewick for more information.

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left.\left(1-\frac{u}{1+u}-\frac{w}{1+w}\right)^{-1}\right|_{u=w=z}\tag{6} \end{align*}

where $$u$$ represents occurrences of $$0$$ and $$w$$ occurrences of $$1$$. Since there are no restrictions stated for zeros we replace occurrences of $$0$$ in a Smirnov word by one or more zeros. \begin{align*}\ u\longrightarrow u+u^2+u^3+\cdots=\frac{u}{1-u}\tag{7} \end{align*}

We substitute (7) in (6) evaluate at $$z$$ and obtain

\begin{align*} \left(1-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z}{1+z}\right)^{-1} &=\left(1-z-\frac{z}{1+z}\right)^{-1}\\ &=\frac{1+z}{1-z-z^2}\\ &=1+2z+3z^2+5z^3+8z^4+\cdots \end{align*}

which is again a generating function of (shifted) Fibonacci numbers.

• Thanks for your answer, especially for the one regarding a), and for the link to the reference to the book! :) – Studentu Mar 22 at 20:53
• @Studentu: You're welcome. :-) – Markus Scheuer Mar 22 at 20:55