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.

My goal is to find the coefficients of the generating function for the following situation:

The number $f(n)$ is the sum over all compositions of $n$ into $3$ parts of the product of those parts. Fo instance, if $n=5$, it can be written as sums of three integers in six ways: $$1+3+1, 3+1+1, 1+1+3, 2+2+1, 2+1+2, 1+2+2.$$

Taking the sum of the products of these groups, we get a number for $f(5)$: $$3+3+3+4+4+4 = 21.$$

I need to find a formula for these numbers. I've solved a few by brute force and I determined that they are the numbers in the 6th diagonal of Pascal's triangle, but I don't want to put that as an explanation. Is there an easy way to do this with generating functions? I would assume that is what is expected of me.

Any insight would be appreciated.

Thanks very much!

Edit: The number of parts is always three, and yes, these are compositions, not partitions. I apologize for any confusion.

share|improve this question
2  
Since you’re taking order into account, these are compositions, not partitions. Is the number of parts always $3$, irrespective of $n$? –  Brian M. Scott Apr 9 '13 at 3:54
    
Are you only considering the compositions that have exactly $3$ parts? I would have guessed that $2+1+1+1$ (and all of its permutations) as well as $1+1+1+1+1$ would be included in your $n=5$. –  Sammy Black Apr 9 '13 at 3:58
4  
I don't understand the downvote. Austin has shown some good thought about the problem. It would be better stated as asking for the number of compositions of $n$ into three parts, which has been provided as an edit. –  Ross Millikan Apr 9 '13 at 4:04

3 Answers 3

up vote 3 down vote accepted

Hint: $(2\cdot 2\cdot 1)\cdot x^{2+2+1} = (2x^2)(2x^2)(x)$. So what could the generating function look like?

Details: If $a_n$ is your count, then we can write:

$$\sum a_nx^n = (x+2x^2+3x^3\dots + nx^n+\dots)^3$$

Do you know a closed form for $\sum nx^n$?

share|improve this answer
    
Ah, alright. So the closed form for $\sum a_nx^n$ is $\frac{1}{(1-n)^2}$, correct? So the entire thing is $\frac{1}{(1-n)^6}$? I just don't totally understand why you chose $nx^n$, mostly because I have a very basic understanding of generating functions. I do think that I understand, however, why you put it to the 3rd power, and I expected that I would have to do that to account for the 3 numbers. –  Austin Apr 9 '13 at 15:36
1  
Well, the closed for is in terms of $x$, not $n$, and no, that is not correct. $$\sum_{n} nx^n = \frac{x}{(1-x)^2}$$. If it was $\sum_{n} nx^{n-1}$ it would be $\frac{1}{(1-x)^2}$, by taking the derivative of $\frac{1}{1-x}$, but we need $x^n$ not $x^{n-1}$. –  Thomas Andrews Apr 9 '13 at 15:38
    
Right, sorry. I meant x, not n. –  Austin Apr 9 '13 at 15:42

HINT: You’re interested in

$$\large\sum_{a+b+c=n\atop{a,b,c\ge1}}abc\;,$$

the sum of all products of three positive integers whose sum is $n$. That looks an awful lot like a convolution, or the sort of coefficient that you’d get in the Cauchy product of three power series. And $a,b$, and $c$ seem to be treated identically, so it’s probably the cube of a single power series. What series?

By the way, you can do it without generating functions. Assume below that $a,b$, and $c$ are always at least $1$.

$$\begin{align*} \sum_{a+b+c=n}abc&=\sum_{a+b\le n}ab(n-ab)\\ &=n\sum_{a+b\le n}ab-\sum_{a+b\le n}a^2b^2\\ &=n\sum_{k=2}^n\sum_{a=1}^{k-1}a(k-a)-\sum_{k=2}^n\sum_{a=1}^{k-1}a^2(k-a)^2\\ &=n\sum_{k=2}^n\left(\frac{k^2(k-1)}2-\frac{k(k^2-1)}6\right)-\dots \end{align*}$$

I shan’t finish this little monster, since it’s the hard way, but it clearly can be finished.

share|improve this answer

The number of compositions of $n$ into three parts is given by ${n-1 \choose 3-1}$ which can be shown by a stars and bars argument. Think of $n$ stars in a row. You need to put two bars in the $n-1$ spaces between them to make your composition. There are ${n-1 \choose 2}$ ways to select the two positions for the bars.

share|improve this answer

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.