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|improve this question
    
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
show 1 more comment

1 Answer

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|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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