Number of ways to interleave two ordered sequences. [duplicate]

Solution 1:

This is the same as taking $m + n$ places, and deciding which $m$ of them get the $x_i$, i.e., $\binom{m + n}{m}$.

For $k$ ordered sequences, the basic idea is the same; you'll get an $k$-nomial coefficient.

Solution 2:

Suppose that you have $k$ ordered lists of elements--where the $j$th list has $n_j$ elements for $1\le j\le k$--and that you wish to interleave them, as described.

Now, all told, there will be $n_1+n_2+\cdots+n_k$ places that we must fill. So, first, we assign the elements of the first list to their places, and since we want to preserve order, then choosing the places will also determine which elements of the first list go to which places. There are $\binom{n_1+n_2+\cdots+n_k}{n_1}$ ways to do this.

Next, we choose which $n_2$ of the remaining places will have members of the second list. There are $\binom{n_2+\cdots+n_k}{n_2}$ ways to do this. We continue in this fashion, until finally we have only the members of the $k$th list to place. There are $\binom{n_k}{n_k}$ ways to do this.

All told, then, there are $$\prod_{i=1}^k\binom{\sum_{j=i}^kn_j}{n_i}$$ ways to interleave the lists in the desired fashion. Still, this expression is a bit ugly. Fortunately, we can make it simpler, by noting that for nonnegative integers $n,r$ with $r\le n$ we have $$\binom{n}{r}=\frac{n!}{r!(n-r)!}.$$ Hence, we're looking at the product $$\frac{(n_1+n_2+n_3+\cdots+n_k)!}{n_1!(n_2+n_3+\cdots+n_k)!}\cdot\frac{(n_2+n_3+\cdots n_k)!}{n_2!(n_3+\cdots n_k)!}\cdots\frac{(n_{k-1}+n_k)!}{n_{k-1}!n_k!}\cdot\frac{n_k!}{n_k!0!}.$$ Since $0!=1,$ then a chain of cancellations show us that this is simply $$\frac{(n_1+n_2+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}=\binom{n_1+n_2+\cdots+n_k}{n_1,n_2,\dots,n_k}.$$