Show the coefficient of $x^3$ in the expansion of $(1+x+x^2+x^3)(1+x^2)(1+x^3)$ is the same as the number of partitions of $3$

Question

(let a partition of $n \in \Bbb N, n>0 $ be a sum of positive integers)

How would you show that the number of different partitions of $3$ is the coefficient of $x^3$ in the expansion of:

$(1+x+x^2+x^3)(1+x^2)(1+x^3)?$

My attempt:

since there are $3$ brackets to choose factors of $x^3$ from, we can say the following:

$ x^3 = x^a x^b x^c, a \in \{0,1,2,3\}, b \in \{0,2\}, c \in \{0,3\}$

The coefficient of $x^3$ in the expansion will equal the number of solutions satisfying $ x^3 = x^a x^b x^c$.

$a=0 \Rightarrow b=0 $ and $ c=3$,

$a=1 \Rightarrow b=2 $ and $ c=0$,

$a=2 \Rightarrow$ no solution.

$a=3 \Rightarrow b=0 $ and $ c=0$,

$\Rightarrow$ the coefficient of $x^3$ is $3$ which equals the number of partitions of $3$.

Do I understand what the question is asking? Because I'm wondering if just multiplying the brackets and obtaining the coefficient is an equivalent solution to the question.

Thanks.

Answer 1

You can see the "situation" as I try and depict in this sketch

For what concerns the partitions of $3$ (and of $2$ and $1$) , all the necessary "pieces" are provided.

Explanation of the sketch
When you expand the first polynomial, this will provide a factor $x^k$ to multiply the rest, and $k$ is either $0$ or $1$ or $2$ or $3$.
The second polynomial will provide a factor $x^j$ with $j=0,2$, and the third a factor $x^n$ with $n=0,3$.
When then you collect the terms $x^{(j+k+n)}$, grouping together all the terms with the exponent $j+k+n=q$, then each of the various terms will correspond to each one of the partitions of $q$ composed of $0..3$ parts $=1$ +$0..1$ parts $=2$ + $0..1$ parts $=3$, and the resulting coefficient of $x^q$ will be the number of those partitions.

Answer 2

Here are two variations, both being equally valid with respect to the stated problem. Maybe the second variant is preferable since it provides some additional insight to the representation of the polynomial.

Algebraic variant:

We calculate the coefficient of $x^3$ of the polynomial and compare it with $p(3)$, the number of partitions.

Since $3$ admits a representation as sum of positive integers without respecting order of summands by \begin{align*} 3&=3\\ &=2+1\\ &=1+1+1 \end{align*} we see $p(3)=3$.

On the other hand using the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial, we obtain \begin{align*} [x^3]&(1+x^3)(1+x^2)(1+x+x^2+x^3)\\ &=\left([x^3]+[x^0]\right)(1+x^2)(1+x+x^2+x^3)\tag{1}\\ &=\left([x^3]+[x^1]+[x^0]\right)(1+x+x^2+x^3)\tag{2}\\ &=1+1+1\tag{3}\\ &=3 \end{align*}

Comment:

• In (1) we consider the coefficient of $[x^3]$ in $1+x^3$ and use the rule \begin{align*} [x^p]x^qA(x)=[x^{p-q}]A(x) \end{align*}

• In (2) we do the same with $1+x^2$ noting that $[x^0]x^2=0$.

• In (3) we select the coefficients of $1+x+x^2+x^3$ accordingly.

Variant based upon generating functions:

If we want to count the number of partitions of a number $n$, we have to consider summands $k$ with $1\leq k\leq n$. The summand $k$ may occur zero, one, two or more times, but at most $\left\lfloor\frac{n}{k}\right\rfloor$ times. The contribution of $k$ encoded as powers of $x$ in a generating function is therefore \begin{align*} 1+x^k+x^{2k}+\cdots+x^{\left\lfloor\frac{n}{k}\right\rfloor k} \end{align*}

In case of $p(n)$ with $n=3$ we have to consider the summands $3,2$ and $1$.

• Summand: $3$ may occur zero or one times giving $\longrightarrow 1+x^3$

• Summand: $2$ may occur zero or one times giving $\longrightarrow 1+x^2$

• Summand: $1$ may occur zero, one, two or three times $\longrightarrow 1+x+x^2+x^3$

We conclude: $p(3)$ is the coefficient of $x^3$ in \begin{align*} (1+x^3)(1+x^2)(1+x+x^2+x^3) \end{align*}