[Math] How many solutions does the equation $n_1 + n_2 + n_3 + n_4 + n_5 = 20$ have in the positive integers if $n_1 < n_2 < n_3 < n_4 < n_5$

combinatorics

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 the number of such distinct arrangements $(n_1, n_2, n_3, n_4, n_5)$ is……
I have no idea how to proceed. Manually, I have done it
$$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$$
$$1+3+4+5+7$$
$$2+3+4+5+6$$
But is there any way I can do it by Permutation and Combination method?

Best Answer

A variation based upon generating functions. We introduce positive integers $a,b,c,d$ and put \begin{align*} n_2&=n_1+a\\ n_3&=n_2+b=n_1+a+b\\ n_4&=n_3+c=n_1+a+b+c\\ n_5&=n_4+d=n_1+a+b+c+d \end{align*}

The equation $n_1+n_2+n_3+n_4+n_5=20$ transforms to \begin{align*} 5n_1+4a+3b+2c+d=20\tag{1} \end{align*} with $n_1,a,b,c,d>0$.

In order to find the number of solutions of (1) we consider the generating function $A(x)$ \begin{align*} A(x)&=\frac{x^5}{1-x^5}\cdot\frac{x^4}{1-x^4}\cdot\frac{x^3}{1-x^3}\cdot\frac{x^2}{1-x^2}\cdot\frac{x}{1-x}\\ &=x^{15}+x^{16}+2x^{17}+3x^{18}+5x^{19}+\color{blue}{7}x^{20}+10x^{21}+\cdots \end{align*} and obtain with some help of Wolfram Alpha the solution \begin{align*} [x^{20}]A(x)\color{blue}{=7} \end{align*}

Add-on: Some details

We first transform the equation with restrictions by introducing positive integers $a,b,c,d$ in an equivalent equation with more convenient restrictions \begin{align*} &n_1 + n_2 + n_3 + n_4 + n_5 = 20\qquad&\qquad&5n_1+4a+3b+2c+d=20\\ &0<n_1<n_2<n_3<n_4<n_5\qquad&\qquad&0<n_1,0<a,0<b,0<c,0<d \end{align*}

We now consider admissible $5$-tuples $(n_1,a,b,c,d)$. Increasing $n_1$ by $1$ adds $5$ to the equation. Similarly, increasing $a$ by $1$ adds $4$ to the equation. We encode these increments via exponents of generating functions:

  • $n_1$: Increment by $5$ gives \begin{align*} x^5+x^{10}+x^{15}+\cdots=x^5(1+x^5+x^{10}+\cdots)=\frac{x^5}{1-x^5} \end{align*}
  • $a$: Increment by $4$ gives \begin{align*} x^4+x^8+x^3+\cdots=x^4(1+x^4+x^8+\cdots)=\frac{x^4}{1-x^4} \end{align*}

and similarly for $b,c$ and $d$. Observe that each of $n_1,a,b,c,d$ is positive, i.e. has at least value $1$. This is respected by smallest values $x^5,x^4,x^3,x^2$ and $x^1$.

The number of admissible solutions is therefore \begin{align*} [x^{20}]&\frac{x^5}{1-x^5}\cdot\frac{x^4}{1-x^4}\cdot\frac{x^3}{1-x^3}\cdot\frac{x^2}{1-x^2}\cdot\frac{x}{1-x}\\ &=[x^{20}]\frac{x^{15}}{(1-x^5)(1-x^4)(1-x^3)(1-x^2)(1-x)}\\ &=[x^{5}]\frac{1}{(1-x^5)(1-x^4)(1-x^3)(1-x^2)(1-x)}\tag{2}\\ &=[x^{5}](1+x^5)(1+x^4)(1+x^3)(1+x^2+x^4)(1+x+x^2+x^3+x^4+x^5)\tag{3}\\ &=\cdots\tag{4}\\ &\color{blue}{=7} \end{align*}

Comment:

  • In (2) we use the coefficient of operator rule: $[x^{p}]x^qA(x)=[x^{p-q}]A(x)$.

  • In (3) we expand the geometric series restricted to powers less or equal to $x^5$ since other terms do not contribute to $[x^5]$.

  • In (4) we expand further and can omit terms with powers greater than $5$.

Hint: Instructive examples can be found in H.S. Wilf's book generatingfunctionology.

Related Question