I have been recently working with generating functions in my discrete mathematics course, and I was interested in one particular generating function. I want to find the generating function for the number of ways one can split $n$ into odd parts. I can see that the first coefficients of the sequence are $$0,1,1,2,2,3,4,5,...$$ And so on. I've been trying to find a recursion, and while it seemed originally that the number of ways looked to be the ceiling of $\frac{n}{2}.$ But it seems like the $6$th coefficient suggests otherwise. Is there another possible recursion going on in this sequence? If so, how would I go about finding the generating function for it?
-
3$\begingroup$ The number of partitions of $n$ into odd parts is the same as the number of partitions of $n$ into distinct parts; the generating function is $$\prod_{k\ge 1}\left(1+x^k\right)=\prod_{k\ge 1}\frac1{1-x^{2k-1}}$$ (see for example here). $\endgroup$– Brian M. ScottJun 13, 2016 at 22:05
1 Answer
The generating function for this sequence is
$f(x)=\prod\limits_{n=1}^{\infty} \cfrac{1}{1-x^{2n-1}}$
since
$f(x)=(1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)\cdots (1+x^{2n-1}+x^{(2n-1)+(2n-1)})\cdots = (1+x+x^2+\cdots)(1+x^3+x^{2\cdot3}+\cdots)\cdots (1+x^{2n-1}+x^{2(2n-1)})\cdots=\cfrac{1}{1-x}\cfrac{1}{1-x^3}\cdots\cfrac{1}{1-x^{2n-1}}\dots=\prod\limits_{n=1}^{\infty} \cfrac{1}{1-x^{2n-1}}$
Moreover, you can express this function as follows,
$\prod\limits_{n=1}^{\infty} (1+x^n)=(1+x)(1+x^2)(1+x^3)\cdots=\cfrac{1-x^2}{1-x}\cfrac{1-x^4}{1-x^2}\cfrac{1-x^6}{1-x^3}\cdots=\cfrac{1}{1-x}\cfrac{1}{1-x^3}\cdots=f(x)$
-
$\begingroup$ The explanation of the last expression of the function $f(x)$ needs more details, but I think it' s fine just like this. $\endgroup$ Jun 13, 2016 at 22:29