What is the number of sequences of positive integers, a1, a2, . . . , an, such that $a_1$ = 1 and $a_{i+1}$ ≤ $a_i$ + 1 for any 1 ≤ i ≤ n − 1 ?
For example the five sequences, 111, 112, 121, 122, 123, satisfy the condition.
(1). For $i>1$, we can have $a_i>1$. Then, we can have a bijective function.
(2). For $i>1$, we can have $a_i=1$. Then, the $a_1, ..., a_n$ can be broken into two parts.
I know (1) and (2) can form Catalan number, but I don't know how to form (1) and (2).
Find the least $k\gt0$ at which $a_{k+1}=1$, or $k=n$ if there is none. Then $(a_2-1,\ldots,a_k-1)$ is an admissible sequence of length $k-1$ and $(a_{k+1},\ldots,a_n)$ is an admissible sequence of length $n-k$. Conversely, concatenating any two admissible sequences whose lengths add to $n-1$, with the first sequence incremented by $1$ and a $1$ prepended, yields an admissible sequence of length $n$, and this mapping is bijective. Thus, if $C_n$ counts the number of admissible sequences of length $n$, we have
$$ C_n=\sum_{k=1}^nC_{k-1}C_{n-k}\;, $$
which is the recurrence relation of the Catalan numbers. Also $C_0=1$ in agreement with the Catalan numbers, so the $C_n$ are in fact the Catalan numbers.