Fdtxjr

I am trying to solve the following problems:

a) Let $mathcalF$ 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 $mathcalF$ 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 $mathcalP$ be the partition in different summands. Then $mathcalP = (epsilon+1) times (epsilon+2)times (epsilon+3)times ...$

$Rightarrow P(z) = (1+z)cdot (1+z^2) cdot (1+z^3) cdot dotsc = frac1(1-z)cdot(1-z^3)cdot(1-z^5)cdot dotsc$

Now let $tildemathcalP$ be the partition in odd summands. Then $tildemathcalP = 1^asttimes3^asttimes5^asttimesdotsc$

$Rightarrow tildeP(z) = frac11-zcdotfrac11-z^3cdotfrac11-z^5cdot dotsc$.

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

c) Let $mathcalK$ be the number of compositions of n into 1s and 2s.
Then $mathcalK = 1,2^ast$ and so $K(z) = frac11-(z+z^2)$.

Let $tildemathcalK$ be the number of compositions of n+2 into 2,3,4,5,6,7,... Then $tildemathcalK = 2,3,4,5,6,...^ast$ and therefore $tildeK(z) = frac11-(z^2+z^3+z^4+z^5+...)$.

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

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

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
$$
frac11-(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+2x^n=sum_n=2^infty k_nx^n-2=frac1x^2sum_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.

Ad c.)

Your approach is fine. With $mathcalK = 1,2^ast$ we obtain
beginalign*
K(z) &= frac11-left(z+z^2right)\
&=frac11-z-z^2tag1
endalign*

and with $tildemathcalK = 2,3,4,5,6,...^ast$ we obtain
beginalign*
tildeK(z) &= frac11-(z^2+z^3+z^4+z^5+cdots)\
&=frac11-fracz^21-ztag2\
&=frac1-z1-z-z^2\
&=1+fracz^21-z-z^2tag3
endalign*

Comment:

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

We obtain from (1) and (3) for $ngeq 1$

beginalign*
colorblue[z^n+2]tildeK(z) &=[z^n+2]left(1+fracz^21-z-z^2right)\
&=[z^n+2]fracz^21-z-z^2tag4\
&=[z^n]frac11-z-z^2tag5\
&,,colorblue=[z^n]K(z)
endalign*

and the claim follows.

Comment:

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




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

Note the coefficients of
beginalign*
K(z)&=frac11-z-z^2\
&=colorblue1+colorblue1z+colorblue2z^2+colorblue3z^3+colorblue5z^4+colorblue8z^5+cdots
endalign*
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
beginalign*
left.left(1-fracu1+u-fracw1+wright)^-1right|_u=w=ztag6
endalign*

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.
beginalign*
ulongrightarrow u+u^2+u^3+cdots=fracu1-utag7
endalign*

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

beginalign*
left(1-fracfracz1-z1+fracz1-z-fracz1+zright)^-1
&=left(1-z-fracz1+zright)^-1\
&=frac1+z1-z-z^2\
&=1+2z+3z^2+5z^3+8z^4+cdots
endalign*

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