Delannoy numberIn mathematics, a Delannoy number describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. The Delannoy numbers are named after French army officer and amateur mathematician Henri Delannoy.
a = np.zeros([m+1, n+1])
a[0,0] = 1 for i in range(1, m+1): a[i,0] = 1 for j in range(1, n+1): a[0,j] = 1 for i in range(1, m+1): for j in range(1, n+1): a[i,j] = a[i1, j] + a[i, j1] + a[i1, j1] return a[m, n] Yeah I've used these paths in bioinformatics programming.
It's directly relevant to comparing two strings for the closest match, when both strings might be tens of thousands of elements long, and have thousands of insertions deletions and changes, of varying lengths without restriction. Lets start at the NW rather than SW corner.
Consider that your top edge is string1 and your left edge is string 2. So matching them, if they are identical, you traverse diagonally, and you want to assign a weight of 0 to this, and come up with an exact match. If there's problems though you will need to do horizontal and vertical jumps for insertions and deletions, which should carry weights, and you'll also need to handle diagonal nonmatch transitions. Now you have a way to score strings for matches, but also, if you are clever, to find the best match pathways for highly different strings without having to actually score every single path. This becomes super easy once you realize you need to add two planes above and below to augment your search, and be able to pop in and out of the third dimension in the traversal. n C r = n! / r! (n  r)!
So obviously r can’t be > n Your idea that you need m + n moves is corrrect Everything else is wrong. You need to move from (0,0) to (m,n)
How is choosing n going to work? You need to choose m up and n right moves. Flip a coin. Heads go right, Tails go up.
Obviously, you flipped m+n times, with m heads, if you wound up at (m, n). Each unique sequence of HHTTHH is a different path. That # is m+n choose m. Oh wait, I thought it was north or east. I didn't see northeast moves were also allowed. Sorry about that.
I found a link. There is a formula, but it's a little more complex. Still simpler than a for loop counting them all.
http://mathworld.wolfram.com/DelannoyNumber.html I bet some bozos give this as an interview question, and ding the candidate when he doesn't know the fancy formula. 

