3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jimmy R. Dec 11 '15 at 16:17
  • 1
    $\begingroup$ @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 $\endgroup$ – Mirko Dec 11 '15 at 16:37
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.