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.

Solutions Collecting From Web of "Number of distinct arrangements {$n_i$} $n_1<n_2<n_3<n_4<n_5$ such that $\sum n_i=20$"

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. 🙂

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.