Paths in a $n \times n$ square grid with diagonal moves allowed : is it possible to simplify the sum

closed-formcombinatoricscomputational complexityfactorialsummation

In another post it was asked to find the number of paths in a $5 \times 5$ square board with diagonal moves allowed.

While answering that question, I found myself thinking about the $n \times n$ grid case.

The total number of paths for a $n \times n$ grid is

$$\sum _{k = 0} ^{n-1} {2(n-1)-k \choose k}{2(n-1)-2k \choose n-k-1} =$$

$$\sum _{k = 0} ^{n-1} \frac{(2(n-1)-k)!} {k![(n-k-1)!]^2}$$

Is there a way to find a simpler form for this sum so that to reduce the computational complexity of the formula?

Just a fast empirical check in Python on the better computational complexity of the formula proposed in the answer of @Gerry Myerson :

Naive implementation of the formula $\sum _{k = 0} ^{n-1} {2(n-1)-k \choose k}{2(n-1)-2k \choose n-k-1} $ :

from math import comb 

def delannoy_1(n) : 

    central_delannoy = 0

    for k in range(0,n) : central_delannoy += comb(2*(n-1)-k,k) * comb(2*(n-1)-2*k,n-k-1)

    return central_delannoy

Implementation of the formula $\sum_{k=0}^n2^k{n\choose k}^2$ :

def delannoy_2(n) :
    
    central_delannoy = 0
    bin_k = 1
    c = 1
    
    for k in range(0,n+1) :
    
        central_delannoy += c * (bin_k * bin_k)

        c *= 2
        bin_k *= n-k-1
        bin_k //= k+1

    return central_delannoy

For $n = 3000$ the second implementation is roughly $300$ times faster than the first one (I have cheated a bit using a better implementation for the second one actually, if I mantain the standard of the first one is just $6$ times faster).

Best Answer

As @BillyJoe notes, these are the central Delannoy numbers. Many formulas are given at the OEIS page. Perhaps the simplest is $$\sum_{k=0}^n2^k{n\choose k}^2$$

Related Question