# Finding a generating-function using partitions

Find a generating function for a , the number of partitions of r into (a.) Even integers (b.) Distinct odd integers.

I am at a loss of starting this.

-
What are 'a' and 'r' meant to be? Could you add a bit more detail? –  Luke Mathieson Mar 1 '13 at 9:23
great question +1. I added some long comments but I hope somone will post a good answer. –  user58512 Mar 1 '13 at 10:35
To start, do you know how to get the generating function for number of partitions with no restrictions? –  Ivan Loh Mar 1 '13 at 10:56

Let $p_E(n)$ be the number of partitions of $n$ into even parts, where we set $p_E(0)=1$. For each $k\in\Bbb Z^+$ let $p_k(n)$ be the number of ways to partition $n$ into parts of size $2k$; clearly

$$p_k(n)=\begin{cases} 1,&\text{if }2k\mid n\\ 0,&\text{otherwise}\;, \end{cases}$$

so $$\sum_{n\ge 0}p_k(n)x^n=1+x^{2k}+x^{2(2k)}+x^{3(2k)}+\ldots=\frac1{1-x^{2k}}\;.$$

By the product rule for ordinary generating functions,

\begin{align*} \sum_{n\ge 0}p_E(n)x^n&=\left(1+x^2+x^4+x^6+\ldots\right)\left(1+x^4+x^8+x^{12}+\ldots\right)\dots\\ &=\prod_{k\ge 1}\frac1{1-x^{2k}}\;. \end{align*}

It’s not hard to see that this infinite product makes sense: the factor $\frac1{1-x^{2k}}$ contributes to the $x^n$ term only if $n\le 2k$.

As an example of what’s going on, the $x^8$ terms are $1\cdot1\cdot1\cdot x^{1\cdot8}$, $x^{1\cdot2}\cdot1\cdot x^{1\cdot6}$, $x^{2\cdot4}$, $x^{2\cdot2}\cdot x^{1\cdot4}$, and $x^{4\cdot2}$, corresponding to the partitions $8$, $2+6$, $4+4$, $2+2+4$, and $2+2+2+2$, respectively.

Suppose that we want to count the partitions of $n$ into distinct parts no larger than $4$. For each of the sizes $1,2,3$, and $4$ we can have either $0$ or $1$ part of that size, so the generating function is $(1+x)(1+x^2)(1+x^3)(1+x^4)$: e.g., the term $1\cdot x^2\cdot1\cdot x^4$, for instance, corresponds to the partition $2+4$ of $6$. Thus, if $p_d(n)$ is the number of partitions of $n$ into distinct parts, we must have

$$\sum_{n\ge 0}p_d(n)x^n=\prod_{k\ge 1}\left(1+x^k\right)\;.$$

How should you modify this to get the generating function for the number of partitions of $n$ into distinct odd parts?

-