# Counting sequences

Identify the amount $x_n$ of sequences $(a_1,\cdots,a_n)$ of integers $\;a_i \geq 0,\;\; 1 \leq i \leq n\;\;$ so that $\;\sum_{i=1}^j a_i \geq j$ for $1 \leq j \leq n - 1\;$ and $\;\sum_{i=1}^n a_i = n. \quad x_0$ is set as 1.

Hint: Try to guess the by first identifying the values for small $n$. Additionally you can use OEIS.

To recap all this I am looking for sequences with $n$ elements where applies:

• All members are positive integers (including 0)
• The sum of all elements is n
• $\sum_{i=1}^j a_i \geq j$ for $1 \leq j \leq n - 1$

As all members are at least 0, the last one is equal to "$a_1 \geq j\;$", isn't it?

For $n=2$ the sequences are (1,1) and (2,0). For $n=3$ it's (1,1,1),(3,0,0),(2,1,0),(2,0,1),(1,2,0).

Am I right? Do you have any hint how to find the answer?

-
there's also $(2,0,1)$. –  Olivier Bégassat Jun 17 '11 at 22:02
A more usual term for "positive integers (including 0)" is "non-negative integers". –  joriki Jun 17 '11 at 22:19
Do you mean $a_i$ wherever you have $u_i$ (or vice versa)? –  Chris Taylor Jun 17 '11 at 22:20
There's also $(1,2,0)$. –  joriki Jun 17 '11 at 22:24
@joriki @Oliver-Bégassat thank you @Chris-Taylor yes, thanks –  muffel Jun 18 '11 at 17:05
show 1 more comment

Consider $a_k$ as the number of steps you go to the right on the $k$-th line of an $n\times n$ square grid. This puts your sequences in bijection with the monotonic paths on an $n\times n$ square grid that don't pass above the diagonal; the number of these paths is the Catalan number $C_n$.
@muffel, draw a $3\times3$ grid. Concentrate on the vertices (the points where the gridlines intersect). Start at the lower-left vertex. Go $a_1$ steps to the right; go up to the next level; go $a_2$ steps to the right; go up to the next level; go $a_3$ steps to the right; go up to the next level. You have turned your triple $(a_1,a_2,a_3)$ into a path from lower left to upper right that only ever goes right and up and never goes above the diagonal. Conversely, any such path give you your kind of triple. –  Gerry Myerson Jun 19 '11 at 0:40