Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share
    
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
1  
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

1 Answer 1

up vote 5 down vote accepted

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

share
    
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.. –  muffel Jun 18 '11 at 17:20
    
@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
    
@Gerry-Myserson just great, thanks! –  muffel Jun 19 '11 at 20:56

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .