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.
Permalink 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]
Permalink 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.
Permalink 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.
Permalink McCain's Tumor 
October 7th, 2018 7:23pm
Cool application, McT.
Permalink X 
October 7th, 2018 7:26pm
Isn't it just m C m+n?  C=combin
Permalink 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.
Permalink Bored Bystander 
October 7th, 2018 9:53pm
I got it reversed, m+n C n.  Still better than the for loop answer.
Permalink 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.
Permalink 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.
Permalink Send private email 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.
Permalink Send private email 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.
Permalink Send private email FSK 
October 8th, 2018 5:06pm

This topic is archived. No further replies will be accepted.

Other topics: October, 2018 Other topics: October, 2018 Recent topics Recent topics