# Number of compositions of n into odd parts

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?

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.$$

• Thank you, you explained it very well! :) Is there any other way how to read the coefficients of K(z) without being familiar with the Fibonacci series? I mean, for example, if one has $\frac{1}{1-z}$ one can do $[z^n]\frac{1}{1-2z} = [z^n]\sum_{j \geq 0}2^jz^j$ = $2^n$. But here we can't even do a partial fraction expansion or anything to get such form, do I see that correctly or am I missing something? Commented Sep 20, 2019 at 19:12
• Could you please be so kind as to answer the questions in my comment, too? I'd very much appreciate that. :) Commented Sep 26, 2019 at 15:19