# Number of permutations of 2n objects of 2 types with order constraint

There are two types of objects: A and B. All objects are indistinguishable from objects of the same type, but not from objects of the other type.

For a given integer n, where there are n objects of each type (so there are 2n objects) I have to find the number of permutations that satisfy the following condition:

Looking at the sequence from the beginning, one must never find more objects of type B than of type A, i.e. the i-th object of type B can only show up if there are at least i objects of type A before it.

Legal sequences would include:

• n=1: A B
• n=2: A A B B / A B A B

Illegal sequences would include:

• n=1: B A
• n=2: A B B A / B A A B / B A B A / B B A A

I know that the total number of permutations is (2n)!/((n!)^2), but I couldn't find out how to get to the number of permutations that satisfy the condition.

Any help is appreciated.

-

This is equivalent to finding the number of paths on a grid from $(0,0)$ to $(n,n)$ that never fall below the diagonal, and the answer is given by the Catalan numbers, which have the recurrence relation $$C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0.$$