Combinatorics: Generating Function related to compositions of a number

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.