Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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
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*}
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}$.
