# Generalizing the Catalan number (enumerative combinatorics)

Consider any sequence consisting of n A's and n B's so that in any of its initial partial segments, the number of B's never exceed the number of A's. It is well known that the number of such sequences is the Catalan number $\frac{1}{n+1}\binom{2n}{n}$.

Now consider sequences consisting of n A's, n B's, and n C's, so that in any initial segments, the number of B's never exceed the number of A's AND the number of C's never exceed the number of B's. Is the number of such sequences known?

-

Yes. This is the generalized ballot problem.

The directed walks on $\mathbb Z_{+}^k$ starting from the origin and ending at $(\lambda_1,\dots,\lambda_k)$, that satisfy $0\le x_1\le \cdots \le x_k$ at every point are in bijection with the number of standard Young tableaux of shape $\lambda$, and this can be found by the Hook-length formula.

In your case we need the number of standard Young tableaux of shape $(n,n,n)$ which is $\frac{2(3n)!}{n!(n+1)!(n+2)!}$.

For even more generality, see the paper "Random walk in a Weyl chamber" by I. M. Gessel and D. Zeilberger.

-
Also: I.Gessel, Super ballot numbers, J. Symbolic Computation 14 (1992), 179--194; people.brandeis.edu/~gessel/homepage/papers/superballot.pdf –  Wadim Zudilin Sep 10 '11 at 6:43