TransWikia.com

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

Mathematics Asked by Min on January 5, 2021

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?

One Answer

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.

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:\ &1cdot0+2cdot 0+3cdot0+4cdot0+color{blue}{5cdot 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}{1cdot1}+2cdot 0+3cdot0+color{blue}{4cdot1}+5cdot0=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}\ &1cdot0+color{blue}{2cdot1}+color{blue}{3cdot1}+4cdot0+5cdot0=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}{1cdot2}+2cdot0+color{blue}{3cdot1}+4cdot0+5cdot0=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}{1cdot1}+color{blue}{2cdot2}+3cdot0+4cdot0+5cdot0=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}{1cdot3}+color{blue}{2cdot1}+3cdot0+4cdot0+5cdot0=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}{1cdot5}+2cdot0+3cdot0+4cdot0+5cdot0=color{red}5\ &color{blue}{x_1=5};x_2=x_3=x_4=x_5=0 end{align*}$$

Answered by Brian M. Scott on January 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP