catalan numbers - counting sequances with sum of 0

Question

I need help in prooving that the cardinal number of the following set is $C_{n}$:

The set of all sequences

$a_{1}, a_{2}, .., a_{n} \in \mathbb{Z} \\ s.t \\ a_{1}+a_{2}+....+a_{n} = 0$

and for every $1 \leqslant i \leqslant n$ , $ a_{i}\geq -1$ and $a_{1}+a_{2}+....+a_{i}\geq 0$

For example, if $n =3$:

the series in the set will be: $(0, 0, 0),(0, 1, −1),(1, 0, −1),(1, −1, 0),(2, −1, −1)$

EDIT: I thought of presenting the problem using parenthesis. Every sequence as a total equal number of "(" and ")". Every sub-sequence has more "(" than ")".

$0$ is presented by "$\color{blue}(\color{blue})$",

$1$ by "$\color{red}($"

$-1$ by "$\color{green})$"

The problem is that the number of parentheses isn't fixed for a given $n$. For example when $n=2$ the series could be $\color{blue}(\color{blue})\color{blue}(\color{blue})$ or $\color{red}(\color{green})$

Also, I don't know how to "translate" the term $ a_{i}\geq -1$

And for $n=3$ the representation of the sequences $(0,1,-1)$ and $(1,-1,0)$ is the same - "$()()$"

Answer 1

Wholly revised; my original idea cannot easily be patched.

$C_n$ is the number of ordered trees with $n+1$ vertices. There is a bijection between these and your sequences of length $n$ as follows. Do a depth-first search (or preorder search, if that terminology is more familiar) through the tree. When each node except the last is first encountered, write down the integer that is $1$ less than the number of children of that node. Ignore the last node.

For $n=3$, for instance, we have the following $C_3=5$ trees with their associated sequences:

     *         *          *          *         *
     |        / \        / \         |        /|\
     *       *   *      *   *        *       * * *
     |           |      |           / \
     *           *      *          *   *
     |
     *
   0,0,0     1,-1,0     1,0,-1     0,1,-1   2,-1,-1

The inverse function is a bit harder to describe but not hard to illustrate. Say we have the sequence $2,1,-1,-1,-1$ for $n=6$; we can build the corresponding tree starting at the top. The root will have $3$ children. The traversal goes next to the first child, which must have $2$ children. Its first child has none, so it’s a leaf. Its second child is another leaf. And the traversal then goes to the root’s second child, which is a leaf. This of course leaves the root’s last child to be a leaf as well, and we have this tree:

             *
            /|\
           * * *
          / \
         *   *

If you’ve not already seen the fact that $C_n$ is the number of ordered trees with $n+1$ vertices, there is a fairly easy bijection between these trees and balanced parenthesis strings. Do a complete depth-first traversal of the tree, starting and ending at the root, and record a left parenthesis when you go down an edge (i.e., away from the root) and a right parenthesis when you go up an edge. The five trees with $4$ nodes shown in the first diagram correspond in order to the strings ((())), ()(()), (())(), (()()), and ()()(); the tree with $6$ nodes shown above yields the string (()())()().

Added: Combining these bijections yields a direct bijection from your sequences to balanced parenthesis strings that isn’t too hard to describe. Given the sequence $\langle a_1,\ldots,a_n\rangle$, begin by writing down a row of $a_1+1$ matched pairs of parentheses and call the first pair the focal pair. Using the sequence $$\langle 3,0,-1,0,1,-1,-1,0,-1\rangle$$ as an example, I start with

$$\color{red}{()}()()()\;,$$

where the focal pair is red. Suppose that you’ve processed $a_k$ for some $k<n$. If $a_{k+1}\ge 0$, place a row of $a_{k+1}+1$ matched pairs of parentheses in the current focal pair and make the first of these pairs the new focal pair; in my example this results in the string

$$(\color{red}{()})()()()\;,$$

where the focal pair is again shown in red. If $a_{k+1}=-1$, however, as is now the case in my example, write nothing and shift the focus to the first empty matched pair to the right:

$$(())\color{red}{()}()()\;.$$

Continue in this fashion to complete the construction of the associated parenthesis string:

$$\begin{align*} a_4=0:&\quad(())(\color{red}{()})()()\\ a_5=1:&\quad(())((\color{red}{()}()))()()\\ a_6=-1:&\quad(())((()\color{red}{()}))()()\\ a_7=-1:&\quad(())((()()))\color{red}{()}()\\ a_8=0:&\quad(())((()()))(\color{red}{()})()\\ a_9=-1:&\quad(())((()()))(())\color{red}{()} \end{align*}$$

This is what I was fumbling towards in my original answer. The associated tree:

                    ----------*----------
                    |        / \        |
                    |       /   \       |
                    *      *     *      *
                    |      |     |
                    |      |     |
                    *      *     *
                          / \
                         /   \
                        *     *