[Math] Number of permutations of 2n objects of 2 types with order constraint

combinatoricspermutations

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.

Best Answer

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.

Related Solutions

Combinatorics – Circular Permutations with Indistinguishable Objects

I wrote a series of blog posts which explains how to solve questions like this; the relevant one is here. The generating function you want is

$$\frac{1}{n} \sum_{d | n} (x_1^{n/d} + ... + x_k^{n/d})^d \varphi \left( \frac{n}{d} \right)$$

where the coefficient of $x_1^{r_1} ... x_k^{r_k}$ is the number you want.

Combinatorics – How to Find Number of k-Permutations of n Objects with x Types

There's probably not going to be an easy way to do this... Consider two different examples of 15-letter "permutations". Then the number of permutations with that multiset of digits depends on the proportions of the chosen digits.

If you really want to do this, you can sum $k!/(s(1)! s(2)! \cdots s(x)!)$ (called the mulitnomial coefficient) over all partitions of $s(1)+s(2)+ \cdots +s(x)=k$ [in this partition s(i) is allowed to be zero and order is important] such that $s(i) \leq r(i)$ for all i. The part s(i) says you have s(i) copies of the i-th letter. The number of permutations with s(i) i-th letters is given as above, by the Orbit Stabiliser Theorem.

Although, this is only one step better than the caveman's counting formula: sum_P 1 where P is the set of permutations you want to count. I.e. just count them one-by-one.

EDIT: While I'm making a few touch-ups, here's GAP code that implements the above formula.

NrPermIdent:=function(k,T)
  local PSet,x;
  x:=Size(T);
  PSet:=Filtered(OrderedPartitions(k+x,x)-1,p->ForAll([1..x],i->p[i]<=T[i]));
  return Sum(PSet,p->Factorial(k)/Product(p,i->Factorial(i)));
end;;

where T is a list of bounds and k is the number of terms in the partition.

For example:

gap> NrPermIdent(15,[4,5,8,3]);
187957770

As another indication that finding a simple formula for these numbers is not going to be easy, observe that NrPermIdent(n,[n,k]) is equal to $\sum_{0 \leq i \leq k} {n \choose k}$ (which is considered a difficult sum to find -- see: https://mathoverflow.net/questions/17202/). I remember reading somewhere (most likely in A=B) that you can prove there is no "closed-form" solution for this.

Best Answer

Related Solutions

Combinatorics – Circular Permutations with Indistinguishable Objects

Combinatorics – How to Find Number of k-Permutations of n Objects with x Types

Related Question