2
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Studentu Sep 20 '19 at 19:12
  • $\begingroup$ Could you please be so kind as to answer the questions in my comment, too? I'd very much appreciate that. :) $\endgroup$ – Studentu Sep 26 '19 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.