5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Do you know about stars and bars argument? Basically, think of this problem as putting 4 bars to divide 20 stars (or points or whatever it is). Each section divided by bars correspond to $n_1,\cdots,n_5$ $\endgroup$
    – user160738
    Aug 21, 2017 at 14:24
  • 4
    $\begingroup$ @user160738 : this doesn't solve very well the problem, since you don't respect the constraint $n_1<...<n_5$ $\endgroup$
    – Evargalo
    Aug 21, 2017 at 14:25

6 Answers 6

7
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Thank You, Can you suggest me some easy problem on this concept so that I can understand it, i understood that you have made each number greater than the other, i will try to use some series of Binomial Theoram $\endgroup$ Aug 21, 2017 at 15:49
  • $\begingroup$ @SamarImamZaidi: I've added some details and a hint for further studies. $\endgroup$ Aug 21, 2017 at 20:27
  • $\begingroup$ @epi163sqrt beautiful answer :) $\endgroup$
    – DatBoi
    May 12, 2022 at 7:20
  • $\begingroup$ @DatBoi: Many thanks for your nice comment. :-) $\endgroup$ May 12, 2022 at 8:02
2
$\begingroup$

Write $$n_1=1+y_1,\qquad n_k=n_{k-1}+1+y_k \quad(2\leq k\leq5)$$ with $y_k\geq0$ $(1\leq k\leq 5)$. Collecting terms we then obtain $$20=\sum_{k=1}^5 n_k=15 + 5y_1+4y_2+3y_3+2y_4+y_5\ .$$ We therefore have to count the solutions of $$\sum_{k=1}^5 z_k\,k=5$$ in integers $z_k=y_{6-k}\geq0$. Each such solution encodes a partition of $5$ into $z_k$ parts of size $k$. Since there are $7$ partitions of $5$, the answer to the original question is $7$.

$\endgroup$
1
$\begingroup$

Numerical algorithm:

Let $S_{m,k}$ count the solutions of $n_1 + n_2 +\cdots + n_k=m$ with $n_1 < n_2 \cdots < n_k$

Let $T_{m,k,t}$ be the same, subject to $n_k=t$. Then $$T_{m,k,t}=\sum_{s=1}^{t-1} T_{m-t,k-1,s}$$

And $S_{m,k}=\sum T_{m,k,t}$. Together with the bondary conditions, this allows to compute $S_{m,k}$

For example (Java, non optimized) https://ideone.com/BZjsmQ

Gives $S(20,5)=7$

$\endgroup$
1
$\begingroup$

Let $m_1 = n_1, m_2 = n_2 -1, m_3 = n_3 -2, m_4 = n_4 -3, m_5 = n_5-4$; then $m_1 \leq m_2 \leq \cdots \leq m_5$ and $m_1+m_2+m_3+m_4+m_5 = 10$. Thus we need the number of 5 partitions of 10, $P(10,5)$. Clearly, $P(10, 5) = 7$, using the recurrence $P(n,p) = P(n-1, p-1) + P(n-p,p)$.

$\endgroup$
0
$\begingroup$

You could start with $1+2+3+4+5 = 15$ and see that you still have to add $5$.

Adding to e.g. $n_3$ implies that you also have to add to $n_4$ and $n_5$, so you need $3$ to do that addition.

So finally you'll end up with $5n_1 + 4n_2 + 3n_3 + 2n_4 + n_5 = 5$.

Which you could try to solve with recursion, either with a program or with a formula. I'm not sure if the formula will be easy and closed form.

$\endgroup$
0
$\begingroup$

Using combinatorics we find that the answer is coefficient of $x^{20} $ in $(x+x^2+x^3+x^4+x^5)(x^2+x^3+..x^6)(x^3..+x^7)(x^4+..+x^8)(x^5+..+x^9)=x^{15}(1+x+x^2+x^3+x^4)^5$ which is $7$ ie ways are $(1,1,1,x,x^4), (1,1,x,x,x^3), (1,1,1,x^2,x^3), (x,x,x,x,x), (1,1,x,x^2,x^2),(1,x,x,x,x^2), (1,1,x,x,x^3) $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .