![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
(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![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
jg26).
As a reassurance: an elegant answer exists.heisenbug already got it so he's not allowed to give the answer away here. ^_^
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. ^_^
