Brainteaser: interleaving ordered sequences

[flexagon]

(This teaser arose naturally from a discussion of concurrence and thread-safety we were having at work yesterday. But I liked it! What an evil interview question it would make.)

If you have two ordered sequences of length 3, for example abc and xyz, there are 20 ways in which you can interleave them while keeping the order of each sequence intact. I won't list all 20, but for example:

abcxyz, abxycz, axbyzc, ... xyzabc.

How many ways can you interleave two sequences of length m and n? We're looking for a closed-form mathematical expression here and will not be impressed by a program that just generates all possibilities (sorry jg26).

As a reassurance: an elegant answer exists. heisenbug already got it so he's not allowed to give the answer away here. ^_^

Comments

[dilletante.livejournal.com]

neat! i'd have to sit down with some paper to make it elegant. um, choose without loss of generality m >= n.

the number of ways of picking x items out of y choices with no regard to order is called "y choose x" in probability; i'd have to look it up to refresh my memory but i think it's y!/x!(y-x)!

for k 1 to n, there are (n-1 choose k-1) ways of grouping n items into k clumps (think of choosing which spaces in between the ordered items to put dividers in). then there are (m+1 choose k) ways of placing those clumps into spaces between the m items of the other set (counting the end spaces). so i think it's going to be the sum from k=1 to n of (n-1 choose k-1) times (m+1 choose k). for n=m=3 this seems to work.

[flexagon]

You might be right (you ARE right about the algebraic expression of combination) but I'm not sure. There's definitely a nicer way of phrasing it. :)

I'm going to put the below in white font to avoid being a spoiler for anyone else. Highlight to see.

The elegant form of the answer is just "(m+n) choose n" (or "(m+n) choose m", they're equivalent). The notation I'm most familiar with for combinations uses a big C with little numbers around it, like _m+nC_n.

This expands to (m+n)! / (m!n!)

For the intuitive reason why this is so, consider that the total length of your combined sequence will always be (m+n). From this, choose any n, that you will fill with the ordered elements of n. The other ones will be filled with the elements of m.

I didn't come up with the intuitive reason; my coworker did after I realized that all the answers we worked out by hand were coming straight from Pascal's triangle, and so the answer must be combination-based, and got the answer just by observing the pattern.

[(Anonymous)]

shoot, now i feel dumb. that's clearly right and much more elegant. in my defense, i was in the car with not much time to think about it. :)