Catalan number basic question - combinatorics

Question

I have a question regarding catalan numbers:

1) Find the number of sequences $a_1 \leq ... \leq a_n$ where $a_i \in \mathbb N$ and $0 \leq a_i \leq i-1$ for all $i \in \{1,2,...,n\}$

For example:

When $n=1$ the only available sequence is: $0$, so only 1 sequence, which is equal to $C_1$.

When $n=2$ the only available sequences are $0,0$ and $0,1$, so 2 sequences, which is $C_2$

When $n=3$ the options are: $0,0,0$ and $0,0,1$ and $0,0,2$ and $0,1,1,$ and $0,1,2$ so 5 options, which is equal to $C_3$ etc...

I know the answer. The answer is $C_n$ (catalan number of index $n$) but I don't understand why. What do catalan numbers have to do with this question?

Answer 1

Catalan numbers count the number of monotonous paths from $(0,0)$ to $(n,n)$ not crossing the diagonal. Interpret each $a_i$ as the max height of the path at $x={i-1}$. Then each of your sequences bijects to a monotonous path through the points $(i-1,\ a_i)$.

Answer 2

Here is one way to see a connection.

Imagine a process which starts with $k=a=0$ and at each step either increases $a$ or increases $k$, where at the end $a=k=n$ and at all stages $a\leq k$. Certainly there are $C_n$ ways for this process to complete (consider $a$ and $k$ as coordinates and the pairs $(k,a)$ obtained during the process as points on a Catalan path). Suppose that whenever we increase $k$ we output the current value of $a$ as $a_k$. Then this process outputs a sequence of the type you are interested in, and similarly every such sequence is output by a unique process of this sort.