# Generating function for counting compositions of $n$

I was given the next question: I was asked to find the generating function for the number of divisions of $n$ (a given natural number) with exactly 3 elements. For example: if $n$ equals to 5 then 3,1,1 are a set of one of the options (3 + 1 + 1 = 5)

I tried thinking about using an exponential generating function but I'm failing to see whether it's right or wrong. Any help will be appreciated!

Repetitions are not allowed

• It seems you are asking for partitions. So, it's better to update the title accordingly. – Markus Scheuer Jan 18 '17 at 17:22

We derive the wanted generating function for the number of partitions of $n$ with exactly three parts by starting with a seemingly different generating function.

The generating function for the number of partitions which consist of zero or more of $1,2,$ and $3$ is \begin{align*} &(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)\\ &\qquad=\frac{1}{(1-x)(1-x^2)(1-x^3)} \end{align*}

Note: The number of partitions consisting of numbers $\leq k$ is the same as the number of partitions with number of parts $\leq k$.

If we use Ferrer diagrams to visualise the situation we see that each partition containing numbers $\leq k$ which is reflected at the main diagonal corresponds with a partition containing $\leq k$ summands.

Since this correspondence is bijective the generating function is the same in both cases.

We conclude a generating function for the number of partitions with exactly three parts is \begin{align*} &\frac{1}{(1-x)(1-x^2)(1-x^3)}-\frac{1}{(1-x)(1-x^2)}\\ &\qquad=\frac{1}{(1-x)(1-x^2)}\left(\frac{1}{1-x^3}-1\right)\\ &\qquad=\frac{x^3}{(1-x)(1-x^2)(1-x^3)}\\ &\qquad=x^3+x^4+2x^5+3x^6+4x^7+\color{blue}{5}x^8+7x^9\cdots \end{align*} The last line was done with some help of Wolfram Alpha.

Example: There are $\color{blue}{5}$ partitions of $8$ with three summands \begin{align*} 8&=1+1+6\\ &=1+2+5\\ &=1+3+4\\ &=2+2+4\\ &=2+3+3 \end{align*}

• Thank you so so much! You're truly amazing. – Lola Jan 18 '17 at 20:43
• @Lola: My pleasure! :-) Good to see the answer is useful! – Markus Scheuer Jan 18 '17 at 20:50
• I have a small question though, How is the representation of 5+ 5+ 5 =15 seen in this explanation? – Lola Jan 18 '17 at 22:08
• @Lola: Reflecting $15=5+5+5$ at the main diagonal gives $15=3+3+3+3+3$. Just transform the rows to columns. – Markus Scheuer Jan 18 '17 at 22:12
• I see! Brilliant !! – Lola Jan 18 '17 at 22:41

If you want only positive elements in the partition or division (as you prefer) of an $n$, then you have to notice that in the expansion of $(x+x^2+...)^3$ the coefficient of $x^n$ counts all the possible ways in which the product of three powers of $x$, one from each parenthesis, give the term $x^n$. This means that their exponents sum to $n$. Thus in the expansion of $(x+x^2+...)^3$ the coefficient of $x^n$ is the number of the desired partitions of $n$. Therefore our generating function is the:

$$\left(\frac{x}{1-x}\right)^3=\left(\frac{1}{1-x}-1\right)^3=(x+x^2+...)^3$$

Of course, we are talking about formal power series. However, from the analytic point of view we should also add that we must have $|x|<1$.

Note: If you wish to find the power series of this generating function, then you should differentiate the geometric series term by term twice and multiply by $\frac{x^3}{2}$.

• But in your answer, there I'm counting one case more than once.. the set 8,2,2 is the same as 2,8,2 – Lola Jan 17 '17 at 20:11
• @Lola I see. Repetitions are not allowed in the triples. If this is the case, then you are right. – Στέλιος Σαχπάζης Jan 17 '17 at 20:15
• Thank you so much for taking the time and effort to try and answer my question, but could you please remove your answer so people could try to answer the question? :) – Lola Jan 18 '17 at 10:46