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)?
Best Answer
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}$.