Take the 2-minute tour ×
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.

I'm not quite sure what the mathematical term for what I'm asking is, so let me just describe what I'm trying to figure out. Let's say that I have two ordered sets of numbers {1, 2} and {3, 4}. I'm trying to figure out the number of possible ways to combine these two sets into one without breaking the ordering of the two sets.

So for instance, {1, 2, 3, 4}, {3, 4, 1, 2}, and {1, 3, 2, 4} are valid combinations, but {2, 1, 4, 3} isn't. How do I figure out the number of valid combinations? This feels like something I should remember from college, but I'm drawing a blank. It feels somewhere in between a combination and a permutation. Maybe I'm looking for a partially-ordered permutation (which seems to be a somewhat difficult concept if google is to be believed)?

share|improve this question
2  
These are called "shuffles" in the algebra literature, sometimes called "interleavings" in computer science. The verb form (to shuffle, or to interleave, two sequences) is more common for the latter. –  T.. Oct 14 '10 at 18:42

2 Answers 2

You are talking about (resulting) tuples I presume (and not sets).

If the sets are $S$ with $s$ elements and $T$ with $t$ elements, then the total possible tuples is $\displaystyle {s+t \choose s}$.

Basically, you have $s+t$ slots and you pick the slots (say $s$) for one of the sets in $\displaystyle {s+t \choose s}$ ways. Once the slots are chosen, all the $s+t$ numbers can now be filled in only one way.

So the total is $\displaystyle {s+t \choose s}$.

share|improve this answer

Here is another way of visualising Moron's answer:

Let $S$ be the first set, and $T$ be the second set. Now, imagine the elements of $S$ are listed, horizontally, in their order; we will not disturb their order, but will only "place" the elements of $T$ among them.

The possible locations for any element of $T$ are (i) before the first elements of $S$; (ii) between two elements of $S$; and (iii) after the last element of $S$. If $S$ has $s$ elements, then this gives $s+1$ possible locations. We can put more than one element of $T$ in each location, though. For example, if $S=\{1,2,3\}$ and $T=\{a,b,c,d\}$, then we can place elements of $T$ either before $1$, between $1$ and $2$, between $2$ and $3$, or after $3$ (four locations); and we could place one element before $1$, none between $1$ and $2$, two between $2$ and $3$, and one after $3$. But note that once we decide where to place the elements of $T$, the order they will appear on is completely determined. If we go the way I just described, you would end up with $a,1,2,b, c, 3, d$, and that is the only way to place elements of $T$ as described while preserving the order.

If we are placing $t$ elements, then, we just need to "select" $t$ locations from $s+1$ possibilities. The order in which we pick them doesn't matter, because in the end we will just put the elements of $T$ in their appropriate order in those locations. And we can select the same location more than once. So we need to compute "combinations with repetitions" (order does not matter, repetitions allowed). The formula for making $n$ selections, with repetitions allowed but where order does not matter, from among $m$ possibilities is $\binom{n+m-1}{n}$ (see for example here) so here we have $n=t$ and $m=s+1$, giving $\binom{t+s}{t} = \binom{t+s}{s}$ possibilities.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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