0
$\begingroup$

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

|cite|improve this question
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is it just $f\cdot g?$ I don't understand why it is if this is the case. $\endgroup$ – AlanH Mar 18 '13 at 23:04
  • $\begingroup$ @Alan: Assuming that you mean the product, making it $$\frac1{1-x}\prod_{n\ge 1}\frac1{1-x^n}\;,$$ yes. Can you pin down what part you don’t understand? $\endgroup$ – Brian M. Scott Mar 18 '13 at 23:06
  • $\begingroup$ Yeah, I meant product. I don't understand why that changes the number of partitions of the integer $n$ to number of partitions that add up to at most $n$. I guess I don't understand the convolution part. The only time I've been introduced to that was in differential equations. $\endgroup$ – AlanH Mar 18 '13 at 23:14
  • 1
    $\begingroup$ @Alan: The coefficient of $x^n$ in the product $$\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)$$ is $$\sum_{k=0}^na_kb_{n-k}\;.$$ If each $b_k=1$, this is just $$\sum_{k=0}^na_k\;,$$ giving you the cumulative total of the $a_k$’s. $\endgroup$ – Brian M. Scott Mar 18 '13 at 23:16

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.