Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have two finite, ordered sequences $x = (x_1,\dots,x_m)$ and $y = (y_1,\dots,y_n)$. How many ways can we create a new sequence of length $m+n$ from $x$ and $y$ so that the order of elements is preserved?

How many ways can we do this using $k$ ordered sequences instead of two?

share|cite|improve this question

marked as duplicate by Cameron Buie, anthus, user127.0.0.1, AlexR, Lost1 Feb 6 '14 at 18:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

you may need some tutorial about combinatorics – dato datuashvili Feb 6 '14 at 17:10
up vote 5 down vote accepted

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.

share|cite|improve this answer

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}.$$

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.