# 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?

-

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)!}$.