Quiz: can you count how many combinations ...

Here's a combinatorics quiz:

If you have 2 ordered lists (lengths N, M), how many ways can they be interleaved into a single list while still preserving the partial ordering from the original lists?

So if the lists were:
List 1: A,B
List 2: X,Y

The following would be valid:

1. A,B,X,Y
2. A,X,Y,B
3. X,Y,A,B
4. A,X,B,Y

But ' yxab' would be invalid since it lists y before x, and the original list 'xy' says y must come after x.

For the full quiz effect, stop reading now and go figure it out! I'll leave the comments moderated so that folks don't give things away.  ( [Update Jan 29] I published the answers) : Read on for hints.

-------------

My wife and I just worked it through and came up with an answer. Our approaches highlighted our different personalities. She started listing out examples while I started by looking for isomorphisms to more easily countable patterns. I ended up seeing an isomorphism in her examples and we found the solution together. 

To verify our answer, I wrote some Python code (run with IronPython) to go through brute-force and count. So the function t(na,nb) enumerates all orderings between 2 lists of sizes na and nb.  In this case, the lists are (a0,a1,a2) and (b0,b1), and there are 10 ways of interleaving them.

 >>> t(3,2)valid= a0 a1 a2 b0 b1valid= a0 a1 b0 a2 b1valid= a0 a1 b0 b1 a2valid= a0 b0 a1 a2 b1valid= a0 b0 a1 b1 a2valid= a0 b0 b1 a1 a2valid= b0 a0 a1 a2 b1valid= b0 a0 a1 b1 a2valid= b0 a0 b1 a1 a2valid= b0 b1 a0 a1 a210

It does a dumb brute-force approach: enumerate all possible interleavings (which is huge) and then just take the ones that preserve the partial ordering (which is much smaller). While it's dumb and slow, it's more convincingly correct than some complex proof. (It optimizes for simplicity).  Here's the code:

 # return a generator listing all orderings of l
# assumes all elements in l are unique
def combo(l):
    #print 'combo:', l
    if (len(l) == 1): yield l
    for head in l:
      rest =  list(l)
      rest.remove(head)
      for x in combo(rest):
        #print 'x=', x
        yield ([head] + x)
        

def verifyHelper(letter, all):
  last = -1
  for x in all:
    if (x[0] == letter):
      if x[1] <= last:
        return False
      last = x[1]
  return True 
  
# verify that the sub sequences are in order
def verify(all):
  return verifyHelper('a', all) and verifyHelper('b', all)

# convert a schedule list to a string for pretty printing,
# eg: a1 b0 a2 b0
def s(l):
  d = ""
  for x  in l:
    d += ('%s%d ' % (x[0], x[1]))
  return d

# Actual counter
def t(na, nb):
  a = [('a', i) for i in range(0, na)]
  b = [('b', i) for i in range(0, nb)]
  all = combo(a + b)
  total = 0
  for x in all:
    if (verify(x)):
      print 'valid=', s(x)
      total += 1
  return total