Calculating permutation of n items under pattern constraints

Question

I am trying to find a formulae that gives the number of unique permutations of an arbitrary number of items, constrained with the following pattern:

For every item X: X' must always appear at some point after X, and never before X

For example, for the following 4 items:

A, A', B, B'

The possible permutations are the following 6:

A, A', B, B'

A, B, A', B'

A, B, B', A

B, B', A, A'

B, A, A', B'

B, A, B', A'

Is there a specific formulae that can calculate this for arbitrary number of items?

Any help is really appreciated.

Thanks a lot.

Answer 1

If you have two items that must be in some order, exactly $\frac 12$ of the permutations satisfy that constraint. If you have two pairs that must each be in a given order ...

Answer 2

Another approach: Say there are $n$ unmarked symbols $A, B, \ldots N$, and $n$ marked symbols $A', B', \ldots N'$.

The first spot must be taken by a marked symbol. There are $n$ to choose from. Say $I$ is placed there. Next, there are $2n-1$ places to choose from regarding where to put $I'$.

Then take the next untaken spot (could be the second spot, could be the third). There are $n-1$ letters to choose from because this too must be taken by an unmarked letter. Let's say $K$ takes that spot. Then there are $2n-3$ spots to choose from to place $K'$.

All in all you get $$ \prod_{i = 1}^n (n-i+1)(2n-2i + 1) = \prod_{i = 1}^n i(2i-1) = n!(2n-1)!! $$ ways to order the letters.