1
$\begingroup$

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?

  • 0
    @joriki: perhaps Bourbaki uses "positive" and "strictly positive"...???2011-06-18

1 Answers 1

5

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

  • 0
    @Gerry-Myserson just great, thanks!2011-06-19