Given a natural number $n$, compute the number of $5$-tuples of natural numbers $(i,j,k,l,m)$ such that $0 \leq i \leq j \leq k \leq l \leq m \leq n$.

Question

I know the general formula for $r$-permutations is $$P(n, r) = \frac{n!}{(n-r)!}$$ but I don't see how this relates to this problem, someone please help!

Answer 1

Hint: Instead of looking at the 5-tuples $(i,j,k,l,m)$ such that $0\leq i\leq j\leq k\leq l\leq m\leq n$, look instead at the related question of finding 6-tuples $(x_1,x_2,x_3,x_4,x_5,x_6)$ such that

$\begin{cases} x_1=i\\ x_2=j-i\\ x_3=k-j\\ x_4=l-k\\ x_5=m-l\\ x_6=n-m\end{cases}$

What can be said about bounds on each of $x_1,x_2,\dots$?

What can be said about the sum $x_1+x_2+x_3+x_4+x_5+x_6$?

Is the set 6-tuples satisfying all of these observed conditions in bijection with the set of 5-tuples satisfying the conditions in the original problem?

How do you count the number of solutions to this modified problem?

Further hint: stars and bars

Answer 2

You have n+1 possible natural numbers to choose from. (have to include 0)

Once you choose 5 the order will be set already - there will only be one way to assign each number to i,j,k,l,m.

So on how many ways can we choose 5 numbers from n+1 numbers, repetition allowed, not sorted: short answer: $\binom{n+1+5-1}{5}$

why? Let's say you have 5 equal balls in a line. Now you'll divide them in n+1 spots with walls and each sort will tell you one way that you choose your 5 numbers.

xi = numbers of times we choose number i x0 + x1 + x2 + x3 + ... xn = 5

Ex. if we choose number 2 three times and number 4 two times:

0+0+3+0+2+0..+0=5

...back to the balls and walls (same example)

||ooo||oo|||..||

number of balls is 5, number of walls is n (in our case it's n, in a general case it's n-1, we started with n+1). Just because to separate k balls in n groups you need n-1 walls.

Now the general formula is $\binom{n+k-1}{k}$. Imagine for a second balls and walls being the same, you get n-1+k elements together. Now out of them choose k elements to be balls.

Answer 3

Thought experiment.

Put $n$ beans unto the table in a row. Put a toothpick exactly between the $i$th bean and the $i+1$th bean. Put another toothpick at exactly the $j$th and the $j+1$th bean and so on. You now have $n$ beans and $5$ toothpicks. Everyway you can place five toothpick among $n$ beans indicates a possible $5$ tuple and every $5$ tuple leads to a way to place beans and toothpicks.

SO the answer is the same as how many ways are there to place $5$ toothpicks among $n$ beans.

Okay, a 2nd thought experiment. You have $n+5$ things and $5$ toothpicks if you have $n+5$ spaces to place things, we need to figure out how many ways there are to choose which of those $n+5$ places will be reserved for toothpicks. So of the $n+5$ spots we need to choose $5$.

The answer is ${n+5} \choose 5$.

=======

The hard way I've done it all my life until I realized it was too hard is:

If you know $i,j,k,l$ then $m$ can be anything from $l$ to $n$ so there are $\sum_{m=l}^n 1$ choices.

If you know $i,j,k$ than $l$ can be anything from $k$ to $n$ and $m$ can be anything from $l$ to $n$ so that is $\sum_{l=k}^n\sum_{m=l}^n 1$

And so on. There are $n+1$ choices for $i$ and $n-i + 1$ choices for $j$ etc.

So the total choices are $\sum_{i=0}^n\sum_{j=i}^n\sum_{k=j}^n\sum_{l=k}^n\sum_{m= k}^n 1$

Which would be a pain to calculate but we can simplify if $n \ge j \ge i$ then there is a $j'$ so that $j = i + j'$ and $n-i \ge j' \ge 0$. So we can reindex the sum as

$\sum_{i=0}^n\sum_{j'=0}^{n-i}\sum_{k'=0}^{n-i-j'}\sum_{l'=0}^{n-i-j'-k'}\sum_{m'= 0}^{n-i-j'-k'-l'} 1$

which is still a pain to calculate...

But the answer is ${n+5} \choose 5$

....

One of the things I've gone decades without noticing is $\sum_{i=0}^n i = \frac {n(n+1)}2 = \frac {(n+1)!}{(n-1)!2!} = {{n+1} \choose 2}$ (!!!!!). A little be of thought experiment of: Suppose I had $n+1$ balls numbered $0..n$, the number of ways to pick two-- there are $n$ possible numbers for the larger ball. If the larger ball is $i$ then there are $0... (i-1)$ or $i$ possible options for the lower ball. So there are $\sum_{i=1}^n i$ ways to choose two balls (!!!).

At bit of thought and $\sum_{i_1=0}^n\sum_{i_2=i_1}^n.... \sum_{i_k=i_{k-1}}^n1 = {{n+k}\choose k}$.