Generating function: number of partitions that add up to at most $n$

565 Views Asked by At

Find a generating function $a_n$, the number of partitions that add up to at most $n$.

So I know that if it were asking the number of partitions of the integer $n$, I would have my generating function as

$$ g(x) = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots} $$

But for now, all I can come up with to handle the "at most" condition is $$ \prod_{r=1}^{m\leq n} \frac{1}{1-x^r}, \text{ for some } m. $$ And I really don't think that this is correct. (No solution provided).

1

There are 1 best solutions below

4
On

HINT: Start with your generating function for $p(n)$:

$$g(x)=\prod_{n\ge 1}\frac1{1-x^n}\;.$$

You want cumulative sums:

$$a_n=\sum_{k=0}^np(k)\;.$$

Therefore you want to convolve the sequence $\langle p(n):n\in\Bbb N\rangle$ with the constant $1$ sequence $\langle 1,1,1,\dots\rangle$, whose generating function is

$$f(x)=\frac1{1-x}\;.$$

What is the generating function of that convolution in terms of $g$ and $f$?