Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 14 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.