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?
Best Answer
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$.