5
$\begingroup$

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)?

  • 5
    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.2010-10-14
  • 0
    http://math.stackexchange.com/questions/382174/ways-of-merging-two-incomparable-sorted-lists-of-elements-keeping-their-relative2016-10-06

2 Answers 2