Find the number of distinct arrangements of 5 unequal positive integers such that their sum is 20

102 Views Asked by At

Let the integers be $n_1, n_2, n_3, n_4$ and $n_5$. It's given in the question that $n_1 + n_2 + n_3 + n_4 + n_5 = 20$.

I thought of taking $n_2$ as $n_1 + a$, $n_3$ as $n_1 + a + b$ and so on... where a, b,... are not equal to 0. So I got this expression:

$5n_1 + 4a + 3b + 2c + d = 20$

After this, I'm not able to continue. How do I proceed?

Thanks in advance.

1

There are 1 best solutions below

0
On

Integer partitions of $n$ into $k$ parts is given by the recurrence

$$p(n,k)=p(n-1,k-1)+p(n-k,k)\tag{1}\label{1}$$

Since a partition of $n$ into $k$ parts either has $1$ as it's smallest part in $p(n-1,k-1)$ ways or it has it's smallest part greater than $1$ in $p(n-k,k)$ ways. This recurrence has $p(n,1)=1$ and $p(1,1)=1$ and $p(1,k)=0$ for $k\gt 1$.

If, say, the integer partition is

$$\sum_{r=1}^{k}n_r=n$$

such that $n_1\le n_2\le \cdots\le n_k$ we make the substitution $n_r'=n_r+(r-1)$ then we have

$$\sum_{r=1}^{k}n_r'-\sum_{r=1}^{k}(r-1)=n$$ $$\implies\sum_{r=1}^{k}n_r'=n+\binom{k}{2}=n'$$

for $n_1'\lt n_2'\lt\cdots\lt n_k'$ this is a bijection between integer partitions of $n$ into $k$ parts and integer partitons of $n'$ into $k$ distinct parts.

In other words the number of partitions of $n'$ into $k$ distinct parts is equal to the number of partitions of $n=n'-\binom{k}{2}$ into $k$ parts.

$$p_d(n',k)=p(n'-\text{C}(k,2),k)$$

In your case $n'=20$ and $k=5$ and $\binom{5}{2}=10$ so $n=20-10=10$.

Reading off $p(10,5)$ in the table formed by the recurrence $\eqref{1}$

$$\begin{array}{cc} &k\\ n&\begin{array}{c|cccccccccccc} p(n,k)&1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\\hline 1 &1&&&&&&&&&&&\\ 2 &1 &1&&&&&&&&&&\\ 3 &1 &1 &1&&&&&&&&&\\ 4 &1 &2 &1 &1&&&&&&&&\\ 5 &1 &2 &2 &1 &1&&&&&&&\\ 6 &1 &3 &3 &2 &1 &1&&&&&&\\ 7 &1 &3 &4 &3 &2 &1 &1&&&&&\\ 8 &1 &4 &5 &5 &3 &2 &1 &1&&&&\\ 9 &1 &4 &7 &6 &5 &3 &2 &1 &1&&&\\ 10 &1 &5 &8 &9 &\bbox[#FFA,10px]{7} &5 &3 &2 &1 &1&&\\ 11 &1 &5 &10 &11 &10 &7 &5 &3 &2 &1 &1&\\ 12 &1 &6 &12 &15 &13 &11 &7 &5 &3 &2 &1 &1\\ \end{array}\end{array}$$

Thus, we have

$$p_d(20,5)=p(10,5)=7\tag{Answer 1}$$

If you want the order of the parts to count then multiply that by $5!$ to give

$$7\cdot 5!=840\tag{Answer 2}$$