Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer
    
Is it just $f\cdot g?$ I don't understand why it is if this is the case. –  AlanH Mar 18 '13 at 23:04
    
@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? –  Brian M. Scott Mar 18 '13 at 23:06
    
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. –  AlanH Mar 18 '13 at 23:14
1  
@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. –  Brian M. Scott Mar 18 '13 at 23:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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