# Number of distinct arrangements {$n_i$} $n_1<n_2<n_3<n_4<n_5$ such that $\sum n_i=20$

Let $n_1<n_2<n_3<n_4<n_5$ be positive integers such that $n_1+n_2+n_3+n_4+n_5=20$.Then what is the number of such distinct arrangements $(n_1,n_2,n_3,n_4,n_5)$?

My Approach :

I assumed

$n_1=t_0+1$

$n_2=n_1+t_1+1$

$n_3=n_2+t_2+1$

$n_4=n_3+t_3+1$

$n_5=n_4+t_4+1$

Where $t_0,t_1,t_2,t_3,t_4 \ge 0$

Now the sum becomes :

$5t_0+4t_1+3t_2+2t_3+t_4=5$

After this, I put the values of $t_i$s $0,1,..$ and so on, and therefore found $7$ Solutions.

My question : Is there another way to solve this question, because as this question was asked in a competitive exam (JEE Advanced), This a very long solution.

• If I have to solve this fast,I use tree (graph) to separate solutions . Mar 9, 2017 at 17:15
• Yes, but do you have any precise mathematical way? Mar 9, 2017 at 17:25
• What if question was n1+n2+n3+n4+n5=50 or 100 or any bigger number, how would have you solved it? Mar 9, 2017 at 17:27
• Are restrict variable in $5t_0+4t_1+3t_2+2t_3+t_4=5$ such as $$5t_0\leq 5 \to t_0=0,1\\4t_1\leq 5 \to t_1=0,1 \\ 3t_2\leq 5 \to t_2=0,1\\2t_3\leq5 \to t_3=0,1,2$$ to reduce the problem ? Mar 9, 2017 at 17:39
• Yes, it'll help for small numbers. Mar 9, 2017 at 17:42

I would say that you start with $1+2+3+4+5=15$ and have to distribute 5 more. And the 5 more have to satisfy the rule that you can't distribute more to the $i$th position than the $i+1$th position.

From that I can come up with the solutions for distributing those 5 faster than I can write them down. They are obviously $(1,1,1,1,1), (0,1,1,1,2), (0,0,1,1,3), (0,0,1,2,2), (0,0,0,1,4), (0,0,0,2,3), (0,0,0,0,5)$ and I count them.

This is obviously a one-off trick and that is appropriate to the actual values chosen. However the described rule comes down to counting the number of partitions of 5. See https://en.wikipedia.org/wiki/Partition_(number_theory) for more on partitions.

As for your harder question with $n_1+n_2+n_3+n_4+n_5=50$, that can be calculated recursively. You want the number of partitions of $35$ into no more than $5$ groups. Well, define $p_{i,k}$ to be the number of partitions of $i$ into no more than $k$ groups. We have the following rules:

1. $p_{0,k} = 1$ (just a string of 0s)
2. $p_{i,1} = 1$ (all go into one)
3. $p_{i,k+1} = p_{i,k} + p_{i-k,k+1}$ (add one to everything)

From here we can work out rules like:

$p_{i,1} = 1$
$p_{i,2} = i+1$
$p_{i,3} = 1 + 2 + ... + (i+1) = (i+1)(i+2)/2$

And so on until we have a formula to use. But finishing that would be harder and not appropriate for the place it appeared. :-)

• Should that be 45 instead of 35. Mar 9, 2017 at 18:02
• @JaideepKhare No, because 1+2+3+4+5 = 15. So we only have 35 more to divide. Just like for 20 we only had 5 left. Mar 9, 2017 at 18:42
• OK, understood. Thanks! Mar 9, 2017 at 18:46
• +1. Note that if the sum had been say $25$ rather than $20$ then the answer would have been the number of partitions of $25-\frac{5(5+1)}2=10$ into up to $5$ parts which I think is $30$ Sep 2, 2023 at 23:37

We can use casework. It is important to be organized to make sure you don't miss any cases.

• Smallest is 1 and then 2:
• $\{1, 2, 3, 4, 10\}$
• $\{1, 2, 3, 5, 9\}$
• $\{1, 2, 3, 6, 8\}$
• $\{1, 2, 4, 5, 8\}$
• $\{1, 2, 4, 6, 7\}$
• We cannot have repeats so that is all
• Smallest is 1 and then 3:
• $\{1, 3, 4, 5, 7\}$
• Smallest is 2
• $\{2, 3, 4, 5, 6\}$

Total, there are $\boxed{7}$ solutions. Surprisingly easy for an JEE problem. This can be solved much faster if you just start listing all numbers.

• Did you change a really big number to 20? If you did then this won't work. I just answered the given problem. Mar 9, 2017 at 17:45
• No, I didn't. In that case even my solution won't work.I was just thinking the possibilities. Mar 9, 2017 at 17:48

Let $$n_1 be positive integers such that $$n_1+n_2+n_3+n_4+n_5=20$$.Then what is the number of such distinct arrangements $$(n_1,n_2,n_3,n_4,n_5)$$?

Alternative approach:

For $$~i \in \{2,3,4,5\},~$$ let $$~y_i~$$ denote $$n_i - n_{i-1}.$$

Then:

• $$~n_1 \geq 1.~$$
• $$y_2,y_3,y_4,y_5,~$$ are all required to be positive integers.
• $$~n_2 = n_1 + y_1.~$$
• $$~n_3 = n_2 + y_2 = n_1 + y_1 + y_2.$$
• Similarly, $$~n_4 = n_1 + y_1 + y_2 + y_3.$$
• Similarly, $$~n_5 = n_1 + y_1 + y_2 + y_3 + y_4.$$

Therefore, you need all positive integer solutions to

$$5n_1 + 4y_2 + 3y_3 + 2y_4 + y_5 = 20. \tag1$$

Notice that if $$~(n_1,y_2,y_3,y_4,y_5) = (1,1,1,1,1),~$$ then $$~x_1 + y_2 + \cdots + y_5 = 15.$$

Let

• $$z_1 = n_1 - 1.$$
• $$z_i = y_i - 1 ~: ~i \in \{2,3,4,5\}.$$

So, the problem has been reduced to determining the number of non-negative integer solutions to

$$5z_1 + 4z_2 + 3z_3 + 2z_4 + z_5 = 5. \tag1$$

At a glance, the possibilities for $$~(z_1, \cdots, z_5)~$$ are:

• $$(1,0,0,0,0).$$
• $$(0,1,0,0,1).$$
• $$(0,0,1,1,0).$$
• $$(0,0,1,0,2).$$
• $$(0,0,0,2,1).$$
• $$(0,0,0,1,3).$$
• $$(0,0,0,0,5).$$

So, there are $$~7~$$ possibilities.