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
    there's also $(2,0,1)$.2011-06-17
  • 0
    A more usual term for "positive integers (including 0)" is "non-negative integers".2011-06-17
  • 1
    Do you mean $a_i$ wherever you have $u_i$ (or vice versa)?2011-06-17
  • 0
    There's also $(1,2,0)$.2011-06-17
  • 0
    @joriki @Oliver-Bégassat thank you @Chris-Taylor yes, thanks2011-06-18
  • 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
    Thanks, I now know that I am heading for the Catalan numbers! Unfortunately I don't get your approach - why does the number of the monothonic paths equals the amount of sequences I am looking for? I just don't see the relation..2011-06-18
  • 0
    @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.2011-06-19
  • 0
    @Gerry-Myserson just great, thanks!2011-06-19