Number of ways to permute $\{1A, 2A, \ldots, NA, 1B, 2B, \ldots, NB\}$ such that the corresponding $iB$ occurs after $iA$?

Question

I am solving a combinatorics problem using dynamic programming. The question asks for

Number of ways to permute $\{1A, 2A, \ldots, NA, 1B, 2B, \ldots, NB\}$ such that the corresponding $iB$ occurs after $iA$ for all $i \in \{1, \ldots, N\}$?

For example, consider $N = 2$, we have 6 permutations $$ (1A,2A,1B,2B) \\ (1A,2A,2B,1B) \\ (1A,1B,2A,2B) \\ (2A,1A,1B,2B) \\ (2A,1A,2B,1B) \\ (2A,2B,1A,1B) $$

There is a recurrence relation between $N$ and $N+1$. Let $f(k)$ denote the number of ways to permute $N = k$, then we see that $$ f(k + 1) = f(k) * \binom{k+3}{2} = f(k) * \frac{(k+3)(k+2)}{2} $$

The binomial coefficient is the number of ways we can insert $(k+1)A, (k+1)B$ with replacement into $k + 2$ locations. We have the following boundary condition: $$ f(0) = 0 \\ f(1) = 1 $$

My question is, is there a closed form solution for this problem? I tried an induction approach, but I didn't recognize any obvious pattern.

Answer 1

There is. There are $(2N)!$ permutations of $\{ 1A, 2A, \ldots, NA, 1B, 2B, \ldots, NB\}$.

We can divide these into groups of size $2^N$, where all the numbers are in the same position but the letters A/B are arranged in all the possible ways. In each such group there will be exactly 1 permutation where $iB$ occurs after $iA$ for all $i$. (Let's call these "good" permutations.)

For example, for $N = 2$ there are $(2\times 2)! = 24$ permutations of $\{1A, 2A, 1B, 2B\}$, and we can divide them into groups of size 4 that contain one "good" permutation. One such group is

$$ (1A,2A,1B,2B) \\ (1A,2B,1B,2A) \\ (1B,2A,1A,2B) \\ (1B,2B,1A,2A) \\ $$

So there are $24/4 = 6$ good permutations with $N = 2$; more generally there are $(2N)!/2^N$ good permutations for a given value of $N$.

Answer 2

The problem is much simpler than you have interpreted it. There are (2n)! ways of arranging the letters. Now, for each arrangement of a and b, we have chosen permutation of that number but we just had to choose them as their order was decided. Hence, we would divide 2 for each combination of A and B. Now that we know the number of combination is n, so we would divide it by 2^n. So the answer would come as (2n!)/(2^n). I think it was easy. If you have any concern then plz comment. I would be obliged to answer you.