RIP Philo

Delannoy number

In 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.
math guy
October 7th, 2018 6:48pm
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[i-1, j] + a[i, j-1] + a[i-1, j-1]

return a[m, n]
cs guy
October 7th, 2018 6:56pm
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.
McCain's Tumor
October 7th, 2018 7:17pm
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 non-match 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.
McCain's Tumor
October 7th, 2018 7:23pm
Cool application, McT.
X
October 7th, 2018 7:26pm
Isn't it just m C m+n?  C=combin
FSK
October 7th, 2018 9:09pm
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.
Bored Bystander
October 7th, 2018 9:53pm
I got it reversed, m+n C n.  Still better than the for loop answer.
FSK
October 7th, 2018 10:17pm
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.
Bored Bystander
October 8th, 2018 5:46am
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.
FSK
October 8th, 2018 5:03pm
Oh wait, I thought it was north or east.  I didn't see northeast moves were also allowed.  Sorry about that.
FSK
October 8th, 2018 5:04pm
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.
FSK
October 8th, 2018 5:06pm