How many sequences $\left\{a_{1}, a_{2}, \ldots, a_{2 n}\right\}$, consisting of ones and minus ones, have the property that $a_{1}+a_{2}+\ldots+a_{2 n}=0$, and all partial sums $a_{1}, a_{1}+a_{2}, \ldots, a_{1}+a_{2}+\ldots+a_{2 n}$ are non-negative?
Let's establish a one-to-one correspondence between such sequences and the placement of parentheses in the product $x_{0} x_{1} \ldots x_{n}$ (including the outer parentheses, for example, $\left(x_{0}\left(\left(x_{1} x_{2}\right) x_{3}\right)\right)$). Specifically, each opening parenthesis is mapped to a one, and each multiplication sign is mapped to a minus one. For instance, the above placement of parentheses in the product $x_{0} x_{1} x_{2} x_{3}$ corresponds to the sequence $\{1,-1,1,1,-1,-1\}$.

The condition for the non-negativity of partial sums is satisfied because each multiplication sign corresponds to its own pair of parentheses, "including" the expressions it multiplies.

Conversely, from each sequence, we can construct a placement of parentheses. First, as indicated above, we place the opening parentheses and multiplication signs in an empty string, then we restore the closing parentheses as follows. Let the opening parenthesis in the sequence correspond to $a_{k}=1$. We find the shortest partial sum $a_{k}+\ldots+a_{m}=0$ (such a sum clearly exists). In this case, $a_{m}=-1$, and we place a closing parenthesis after the multiplication sign corresponding to $a_{m}$. Then it is easy to insert the variables $x_{0}, \ldots, x_{n}$ into the resulting string.

## Answer

$C_{n}$.