Number of compositions of n into odd parts

Question

I am trying to find the number of compositions of a natural number n into odd parts by using the "operator approach". (I'm not sure if this is how the method is called in English. But the method I'm trying to use is the one described, f.e. in the book "Analytic Combinatorics" by Flajolet and Sedgewick. On page 48 there is described how to get the number of partitions of n into odd parts, but not the compositions.)

My idea so far is that $\mathcal{K_{odd}} = SEQ(\{1,3,5,7,9, \dotsc\})$ and therefore the generating function is

$K_{odd}(z) = \dfrac{1}{1-(z+z^3+z^5+z^7+\dotsc)} = \sum_{j \geq 0} (\sum_{k=1\\k\, odd}^n z^k)^j$.

But now I'd have to read the coeffizient of $z^n$ from it and I have no idea how to manage this. So maybe my considerations are wrong so far?

I'd be glad if you could help, thanks in advance!

Answer 1

The key is that $z+z^3+\cdots = \frac{z}{1-z^2}.$ So you get:

$$K_{odd} = \frac{1}{1-\frac{z}{1-z^2}}=\frac{1-z^2}{1-z-z^2}=1+\frac{z}{1-z-z^2}$$

If you already know that $\frac{z}{1-z-z^2}$ is the generating function for the Fibonacci sequence, $F_0=0,F_1=1, F_{n+1}=F_n+F_{n-1},$ then you see the coefficient of $x^n$ is: $1=F_0+1$ when $n=0$ and $F_n$ for general $n.$

---

We might now try to prove it directly, given that we already know the answer. If $K_n$ be your coefficients. It is easy to show that $K_{0}=K_{1}=K_{2}=1.$

Next, you need to show that $K_{n+1}=K_{n}+K_{n-1}$ for $n\geq 2.$ Not sure how to do that, but there might be a counting argument.

If $n+1=a_1+\cdots+a_k$ where the $a_k$ are odd, then if $a_1=1$ we remove the first $1$ and get a sum to $n.$ And if $a_1>1$ replace $a_1$ with $a_1-2$ to get a sum of $n-1.$

So we get $K_{n+1}=K_n+K_{n-1},$ for $n\geq 2.$

---

This is basically a bijection between the set of sums to $n+1$ and the set of sums to $n$ and $n-1.$ If $S_n=\{(a_1,\cdots,a_k)\mid a_i\text{ odd and } a_1+\cdots+a_k=n\}$ then we have a bijection $f:S_{n+1}\to S_n\sqcup S_{n-1}$ where $$f(a_1,\cdots,a_k)=\begin{cases}(a_2,\dots,a_k)\in S_n&a_1=1\\ (a_1-2,a_2,\dots,a_k)\in S_{n-1}&a_1>1\end{cases}$$

and $$f^{-1}(a_1,\dots,a_j)=\begin{cases}(1,a_1,\dots,a_j)&(a_1,\dots,a_j)\in S_n\\ (a_1+2,a_2,\dots,a_j)&(a_1,\dots,a_j)\in S_{n-1}\end{cases}$$

Note that $f^{-1}$ doesn't for when $n=1$ in the case $S_{n-1}$ because the element of $S_0$ is the empty list, so there is no $a_1.$ Thus, we don't have $K_{n+1}=K_n+K_{n-1}$ when $n=1.$