Take the 2-minute tour ×

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer


