<s>[INST] 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!
 [/INST] 
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.

</s>