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.$$

The Catalan numbers are one of those sequences that pop up again and again in combinatorics. They're worth knowing.

It would probably be instructive for you to convince yourself that your problem does in fact have the recurrence relationship above.

  • $\begingroup$ I guess I should have known... wasn't the first time people told me / I found out that Catalan numbers are magic. Thanks a lot :) $\endgroup$ – Waboodoo Jan 24 '13 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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