# Sequences of integers $0=a_1\leq a_2\leq\ldots\leq a_n$ such that $a_k<k$ for every $1\leq k\leq n$

I'm trying to find the number of sequences of integers $0=a_1\leq a_2\leq\ldots\leq a_n$ such that $a_k<k$ for every $1\leq k\leq n$.

I know for $n=3$, the sequences are $000, 001, 002, 011,012$, so the number of sequences is $5$, but I don't know how to approach this further.

Any tips?

## 2 Answers

The solution to your problem are the ultra-famous Catalan Numbers. Have a look at Wikipedia.

• The $a_k$'s may be interpreted as the column height of a monotonic lattice path that is not allowed to pass the diagonal. See the link above. – Jimmy R. Dec 11 '15 at 16:17
• @Stef Where exactly is "the link above", could you please include it to make your comment self-contained? I could not find it. Here is a link to Catalan Numbers on Wikipedia, if this is what you (and the answer poster) meant – Mirko Dec 11 '15 at 16:37

I don't know if there's an easy formula, but you can get the answer in terms of a recurrence which you can evaluate by hand for small $n$ or use a fast computer program for large $n$. Note that a valid sequence for $n$ gives a valid sequence for $n+1$ as long as $a_{n+1} \geq a_n$ and $a_{n+1} < n+1$. So if you let $c_{n,m}$ be the number of sequences of length $n$ that end in $m$, you get

$$c_{n+1,m} = \sum_{j=0}^m c_{n,j}$$

and then your total count is $c_n = \sum_{m=0}^{n-1}c_{n,m}$