Number of sequences satisfying certain constraints

Question

I've got this problem from a contest training that was held today at my school, the competition is not ongoing, in fact I will provied here the link to the solutions: Problem's solutions

That being said, I felt the solution to one of the problems was kinda lame since it relied on you knowing the theory behind Catalan numbers, the problem is the following:

How many sequences are there, such that $a_i\ge 0 ,\forall i $, $a_0=a_{18}=0$ and $a_i=a_{i-1}\pm1$ $\forall 1\le i\le 18$

My attempt: I didn't get very far in this one, I drew a table with 19 blank spots, put a zero at the beginning, one at the end, and then tought I could just use simple permutations (Basically count the number of sequences just by counting the number of ways there are to put eight "+1's" and eight "-1's" and divide by the permutation of the repeated elements, so $\frac{16!}{8!\cdot 8!}$, then I remembered that $a_i \ge 0$ for all $i$ condition, and got stuck, I tought I could maybe use engineer's induction (analyze small cases) but I decided to just move onto other problems, any insight on this one is much appreciated.

Also, the answer according to the solutions is the nineth catalan number, $C_9=\frac{1}{10}{18 \choose 9}=4862$

Answer 1

This is a tough problem, and I imagine there is no way to solve it without some prior knowledge of the Catalan numbers.

For each $1\le i\le 18$, let $d_i=b_i-b_{i-1}$, so that $b_i=d_1+d_2+\dots+d_{i}$. Each $d_i=\pm1$. Now, consider the list of $19$ numbers $$ (1,d_1,d_2,\dots,d_{18})\tag{$*$} $$ Since each $b_i\ge 0$, each partial sum $1+d_1+\dots+d_i$ of this list is strictly positive, and the sum of the entire list $1+d_1+\dots+d_{18}$ is equal to $1$.

How many ways are there to choose such a list $(*)$ of $19$ numbers, all equal to $\pm1$, whose sum is $1$? Well, clearly there must be exactly $9$ numbers which are $+1$ and $8$ which are $-1$. The number of sequences would then be $\binom{19}{10}$. However, this is ignoring the condition that all partial sums must be positive. We now appeal to this result.

Lemma: Let $(d_1,\dots,d_{n})$ be a list of $n$ integers summing to $1$. Exactly one of the $n$ rotations of this list has the property that all of its partial sums are positive. A rotation by $k$ is the list $(d_{k+1},d_{k+2},\dots,d_n,d_1,\dots,d_{k})$.

Since there are $\binom{19}{10}$ lists of $\pm1$ whose sum is $1$, and exactly $1$ out of $19$ of those lists have all partial sums positive, it follows that the number of lists like $(*)$ is $$ \frac1{19}\binom{19}{10}=\frac1{10}\binom{18}9. $$

I leave it to you to prove the Lemma.

Answer 2

Here is a solution that, while computationally demanding, is quite elementary and intuitive. Note that $a_i\leq 9$, with $a_i=9$ only when $i=9$ - which is why a triangular shape is formed below. The spreadsheet's red labels indicate how many paths get to a certain point. For example, there is only $2$ possible 'paths' to reach $a_3=1$. We could have $a_0=1,a_1=1,a_2=2,a_3=1$ or $a_0=1,a_1=1,a_2=0,a_3=1$. And notice that the number of paths to reach a certain point is equal to the number of paths that reach the one or two points that precede it - since any path to a certain point will pass through one of its preceding points.

Thus all we have to do is compute a few points and work out the rest, forming subsequent points by adding up the values of its preceding points. Once we do this enough, we'll eventually find that the number of possible paths to $a_{18}=0$ is $4862$, meaning that there are $4862$ such sequences.