Solving combinatorial problems with symbolic method and generating functions

Question

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!

Answer 1

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.

Answer 2

Ad c.)

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:

• In (2) we use the geometric series expansion.

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.

ad a.)

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.