I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, from the words $ab$ and $cd$ one can form:
$$abcd, acbd, acdb, cdab, cadb, cabd$$
If the first word has length $n$ and the second word has length $m$, then the ways of doing this translates into
$$t(n,m) = t(n-1, m) + t(n,m-1)$$
with the initial conditions $t(0,m)=1=t(n,0)$, where $n,m \geq 0$. How can one figure out a closed form for this? Since this is part of a computer program, I really only need a fast algorithm for computing it. However, the standard way of memoizing the calls and using the recursion directly won't work, because the numbers $n,m$ can be of the order of $2^{32}$.
It's simply $\binom{m+n}m=\binom{m+n}n$: once you choose $n$ positions for the first word, the entire meshed string is completely determined.