Explain why the number of integer solutions is equal to the number of integer partitions of $n$

Question

I have to explain how the number of integer solutions to $x_1 + 2x_2 + 3x_3 + \dots + nx_n = n$ with $x_i \ge 0$ for $i = 1,2,\dots,n $ is equal to the number of integer partition of $n$.

I made an attempt. Assume $x_1 = a_1, x_2 = a_2, \dots , x_n = a_n$ Then we have a partition of $n$ equal to $a_1 + 2a_2 + 3a_3 + \dots + na_n = n$

$$\Rightarrow (1 + 1 + \cdots + 1) + (2 + 2 + \cdots + 2) + \cdots + (n + n + \cdots + n) = n$$

Got up this point, but I don't know what to do next. Can you help?

Answer 1

HINT: A partition of $n$ is completely specified when we know the number of parts of each size. For instance, the partition $2+2+2+1+1$ of $8$ is completely specified by saying that it has $3$ parts of $2$ and $2$ parts of $1$. Interpret the numbers $x_1,\ldots,x_n$ as numbers of parts in some way. I’ve put a further hint in the spoiler-protected box below.

$x_1+x_2+\ldots+x_n$ is the total number of parts in the partition corresponding to that solution to the equation.

Added: Here is an example to illustrate more fully the correspondence between solutions in non-negative integers to $$1x_1+2x_2+3x_3+\ldots+nx_n$$ and partitions of $n$. Specifically, I’ll match each of the $7$ partitions of $5$ with the corresponding solution to $1x_1+2x_2+3x_3+4x_4+5x_5=5$.

$$\begin{align*} &\color{red}5=\color{blue}5:\\ &1\cdot0+2\cdot 0+3\cdot0+4\cdot0+\color{blue}{5\cdot 1}=\color{red}5\\ &\color{blue}{x_5=1};x_1=x_2=x_3=x_4=0\\ &\\ &\color{red}5=\color{blue}{4+1}\\ &\color{blue}{1\cdot1}+2\cdot 0+3\cdot0+\color{blue}{4\cdot1}+5\cdot0=\color{red}5\\ &\color{blue}{x_4=1,x_1=1};x_2=x_3=x_5=0\\ &\\ &\color{red}5=\color{blue}{3+2}\\ &1\cdot0+\color{blue}{2\cdot1}+\color{blue}{3\cdot1}+4\cdot0+5\cdot0=\color{red}5\\ &\color{blue}{x_3=1,x_2=1};x_1=x_4=x_5=0\\ &\\ &\color{red}5=\color{blue}{3+1+1}\\ &\color{blue}{1\cdot2}+2\cdot0+\color{blue}{3\cdot1}+4\cdot0+5\cdot0=\color{red}5\\ &\color{blue}{x_3=1,x_1=2};x_2=x_4=x_5=0\\ &\\ &\color{red}5=\color{blue}{2+2+1}\\ &\color{blue}{1\cdot1}+\color{blue}{2\cdot2}+3\cdot0+4\cdot0+5\cdot0=\color{red}5\\ &\color{blue}{x_2=2,x_1=1};x_3=x_4=x_5=0\\ &\\ &\color{red}5=\color{blue}{2+1+1+1}\\ &\color{blue}{1\cdot3}+\color{blue}{2\cdot1}+3\cdot0+4\cdot0+5\cdot0=\color{red}5\\ &\color{blue}{x_2=1,x_1=3};x_3=x_4=x_5=0\\ &\\ &\color{red}5=\color{blue}{1+1+1+1+1}\\ &\color{blue}{1\cdot5}+2\cdot0+3\cdot0+4\cdot0+5\cdot0=\color{red}5\\ &\color{blue}{x_1=5};x_2=x_3=x_4=x_5=0 \end{align*}$$