You can construct a sequence of 5 numbers $(a,b,c,d,e)$ with the following rule:
$a\in\{1\}$
$b\in\{2,3\}$
$c\in\{3,4,5\}$
$d\in\{4,5,6,7\}$
$e\in\{5,6,7,8,9\}$
How many sequence are strictly ordered?
I tried to solve this problem and with some empirical attempt I found that the answer is 42. Are anyone able to give an elegant proof about that?
On
The Catalan number $Cn$ is the number of monotonic lattice paths along the edges of a grid with $n × n$ square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting our sequence as I show in the following picture:
Indeed we have $C_5=42$.
Here's an idea. (Though not necessarily one that I'd call "elegant," it might still be an improvement.) For brevity, I will refer to strictly ordered sequences as "good," and the rest as "bad."
If $d=4,$ then there are $5$ distinct ways that $a,b,c$ could have been chosen such that regardless of our choice of $e,$ the sequence is bad. The remaining possible choice of $a,b,c$ will necessarily yield a good sequence. Hence, there are $5$ good sequences such that $d=4.$
If $d=5,$ there are $3$ possible ways to choose $a,b,c$ such regardless of our choice of $e$, the sequence is bad. For each of the remaining three possible ways to choose $a,b,c,$ there are $4$ ways to choose $e$ so that the sequence is good. This gives us $12$ good sequences such that $d=5.$
If $d=6,$ there is only one way to choose $a,b,c$ such that regardlessof pur choice of $e$, the sequence is bad. For each of the remaining $5$ ways to choose $a,b,c,$ there are $3$ ways to choose $e$ so that the sequence is good. This gives us $15$ good sequences such that $d=6$.
The $d=7$ case is similar to the $d=6$ case, and gives us $10$ more good sequences.
Hence, there are $42$ good sequences.