# Number of non-decreasing sequence $\{a_i\}$ such that every $a_i \geq i$

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?
• 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. Jul 17 '20 at 11:31
• @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\}$ Jul 17 '20 at 11:48
• @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 Jul 18 '20 at 11:36

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$$.