Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 :) –  Waboodoo Jan 24 '13 at 16:32
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.