Ways of merging two incomparable sorted lists of elements keeping their relative ordering

Question

Suppose that, for a real application, I have ended up with a sorted list A = {$a_1, a_2, ..., a_{|A|}$} of elements of a certain kind (say, Type-A), and another sorted list B = {$b_1, b_2, ..., b_{|B|}$} of elements of a different kind (Type-B), such that Type-A elements are only comparable with Type-A elements, and likewise for Type-B.

At this point I seek to count the following: in how many ways can I merge both lists together, in such a way that the relative ordering of Type-A and Type-B elements, respectively, is preserved? (i.e. that if $P_M(x)$ represents the position of an element of A or B in the merged list, then $P_M(a_i)<P_M(a_j)$ and $P_M(b_i)<P_M(b_j)$ for all $i<j$)

I've tried to figure this out constructively by starting with an empty merged list and inserting elements of A or B one at a time, counting in how many ways each insertion can be done, but since this depends on the placement of previous elements of the same type, I've had little luck so far. I also tried explicitly counting all possibilities for different (small) lengths of A and B, but I've been unable to extract any potential general principle in this way.

Answer 1

The merged list has length $|A|+|B|$. Once you know which $|A|$ positions in it are occupied by the elements of list A, you also know exactly how the whole thing has to be ordered, since the internal orders of the elements of A and the elements of B are already known. Thus, there are $$\binom{|A|+|B|}{|A|}=\binom{|A|+|B|}{|B|}$$ possible merged lists, one for each choice of $|A|$ positions for the elements of list A.

Answer 2

$\frac{(m+n)!}{(m)!(n)!}$; where m,n is the length of the arrays. $(m+n)!$ is the total number of ways of arranging without any restriction. The condition given that you can not change the order of each array so you should not change the order of each array , so we need to divide all the permutations of each array!

Answer 3

For merging N sorted lists, here is a good way to see that the solution is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!\dots |A_N|!}$$

All the $(|A_1|+\dots|+|A_N|)$ elements can be permuted in $(|A_1|+\dots|+|A_N|)!$ ways. Among these, any solution which has the ordering of the $A_1$ elements different from the given order have to be thrown out. If you keep the positions of everyone except $A_1$ fixed, you can generate $|A_1|!$ permutations by shuffling $A_1$. Only 1 among these $|A_1|!$ solutions is valid. Hence the number solutions containing the right order of $A_1$ is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!}$$

Now repeat the argument for $A_2$, $A_2, \dots A_N$.