1
$\begingroup$

Find the number of non-decreasing sequences $a_1, a_2, a_3, a_4, a_5$ such that $a_i \geq 1$, $a_5 \leq 20$ and $a_i \geq i$;

My attempt

I tried to use the Inclusion-Exclusion principle, the number of non-decreasing sequences $a_1, a_2, a_3, a_4, a_5$ such that $a_i \geq 1$,$a_5 \leq 20$ is ${24\choose5}$, However, I am having trouble counting the number of such sequences so that there is some $a_i \lt i$. I tried to seperate them into $4$ cases $\{a_1, 1, a_3, a_4, a_5\}$, $\{a_1, a_2, 2, a_4, a_5\}$, $\{a_1, a_2, a_3, 3, a_5\}$, $\{a_1, a_2, a_3, a_4, 4\}$, but there are lots of overlapping cases and I do not want to handle them.

Question

  • Should I use Inclusion-Exclusion principle here? If yes, is there any smarter way than mine?
  • What is the most efficient way to find the answer?
$\endgroup$
3
  • $\begingroup$ Hint: Consider all sequences of distint numbers and order them-they automatically fulfill the requirements, you have $\binom{20,5}$ possibilities, now consider the cases of multiple equals seperately. $\endgroup$
    – IMOPUTFIE
    Jul 17 '20 at 11:31
  • $\begingroup$ @IMOPUTFIE Thanks for the hints, but I have another question, consider the case of the form $\{a,a,b,c,d\}$, I should use inclusion-exclusion right? Because the only case for this to be invalid is $\{1,1,a,b,c\}$ $\endgroup$ Jul 17 '20 at 11:48
  • $\begingroup$ @IMOPUTFIE Can you elaborate? While I understand Brain's approach, I would really want to know how do you consider the cases of multiple in an organised way $\endgroup$ Jul 18 '20 at 11:36
2
$\begingroup$

I found it easiest to convert it to a problem in counting paths on the integer lattice in the plane: it can be solved using the reflection method, one of the standard ways to show that $C_n=\frac1{n+1}\binom{2n}n$, where $C_n$ is the $n$-th Catalan number.

Suppose that $\langle a_1,\ldots,a_5\rangle$ is such a sequence. We can interpret it as directions for a walk on the integer lattice in the plane, starting at the origin: we first take $a_1$ steps north to $\langle 0,a_1\rangle$, then one step east to $\langle 1,a_1\rangle$, then $a_2-a_1$ steps north to $\langle 1,a_2\rangle$ and one step east to $\langle 2,a_2\rangle$, and so on, finishing by taking $20-a_5$ steps north from $\langle 5,a_5\rangle$ to $\langle 5,20\rangle$; the requirement that each $a_k\ge k$ is then the requirement that this path never drop below the diagonal $y=x$. Moreover, each NE path (i.e., a path using only steps to the north and to the east) from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that never drops below the diagonal corresponds to a unique sequence $\langle a_1,\ldots,a_5\rangle$ satisfying the conditions of the problem, so our problem reduces to counting such paths.

Suppose that a path first drops below the diagonal at $\langle k,k-1\rangle$; after that point it must take $5-k$ steps to the east and $21-k$ to the north. If we reflect it in the diagonal, we get a path starting at $\langle k,k-1\rangle$ and taking $21-k$ steps to the east and $5-k$ steps north and thus ends at $\langle 21,4\rangle$. Conversely, any NE path from $\langle 0,0\rangle$ to $\langle 21,4\rangle$ must stay on or above the diagonal until it hits a point of the form $\langle k,k-1\rangle$, and reflecting the remainder of the path in the diagonal gives us a path from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that first drops below the diagonal at $\langle k,k-1\rangle$.

There are clearly $\binom{25}5$ NE paths from $\langle 0,0\rangle$ to $\langle 5,20\rangle$. There is a bijection between those that drop below the diagonal and NE paths from $\langle 0,0\rangle$ to $\langle 21,4\rangle$, and there are $\binom{25}4$ of those, so there are $$\binom{25}5-\binom{25}4=53130-12650=40480$$ NE paths from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that do not drop below the diagonal.

More generally, the number of non-decreasing sequences $a_1,\ldots,a_n$ such that $a_1\ge 1$, $a_k\ge k$ for $k=1\ldots,n$, and $a_n\le m$ is

$$\binom{n+m}n-\binom{n+m}{n-1}=\binom{n+m}n-\frac{n}{m+1}\binom{n+m}n=\frac{m+1-n}{m+1}\binom{n+m}n\;.$$

When $m=n$ this reduces to $C_n=\frac1{n+1}\binom{2n}n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.