Number of Sequences

[sylar]

1. The problem statement, all variables and given/known data

In how many ways can we form a sequence of non-negative integers a_1,a_2,...,a_(k+1) such that the difference between the successive terms is 1 (any of them can be bigger) and a_1 =0.


2. Relevant equations



3. The attempt at a solution

For k=1, there is only one way: 01. For k=2, there are two ways: 012 or 010. For k=3, there are three ways: 0121,0123 or 0101. For k=4 there are six ways: 01210,01212,01232,01234,01010 or 01012. Note that when k is even, the number of such sequences is twice the number of such sequences when we have k-1 because when k is odd, there is no possibility for the sequence to finish with 0, and so we can add both of the two possible choices to the end of the sequence. But i couldn't find a nice formula relating the case k is odd to the one k is even? Can you help me with this?

Note: There are 10 ways for k=5, 20 ways for k=6 and 35 ways for k=7.

[jhicks]

I don't think there's a way to describe both in the same way. The conditions for creating new sequences is slightly different depending on whether k is odd or even (as you realized).

[sylar]

The results of this problem are quite interesting to me. When k is an even integer, say 2n, then the number of such ways is C(2n n); and when k is an odd integer, say 2n+1, the number of such ways is C(2n+1 n). Also i found that for k odd, say 2n+1, the number of ways to realize our aim is [(2*the number of such ways for k=2n) - C_n],where C_n denotes the Catalan number, I couldn't find a nice way to prove the above claim (which is obviously true). Can you demonstrate why these are true?