# Combinatorics: Generating Function related to compositions of a number

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.

• 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
• 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

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

• 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
• 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
• @ThomasAndrews, me too don't know how the $(x + 2x^2 + \cdots)^3$ counts to 21. could you please elaborate a little bit more ? – ramgorur Oct 19 '16 at 21:13

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.

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.