Delannoy numbers

Question

Consider a grid from \$(0,0)\$ in the bottom-left corner to \$(m,n)\$ in the top-right corner. You begin at \$(0,0)\$, and can only move in one of these three ways:

• Directly north \$(+0, +1)\$,
• Directly east \$(+1, +0)\$, or
• Directly north-east \$(+1, +1)\$

How many different paths are there from your start at \$(0,0)\$ to \$(m, n)\$?

For example, if you're trying to reach \$(3, 3)\$, there are 63 different paths:

This value is given by \$D(m,n)\$, the Delannoy numbers. One formula for these numbers is

$$D(m,n) = \begin{cases} 1, & \text{if } m = 0 \text{ or } n = 0 \\ D(m-1, n) + D(m-1, n-1) + D(m, n-1), & \text{otherwise} \end{cases}$$

Others can be found on the Wikipedia page

---

You are to take two non-negative integers \$n\$ and \$m\$ and output \$D(m,n)\$. This is code-golf, so the shortest code in bytes wins

You may input and output in any convenient manner, and you may assume that no part of the calculation exceeds your language's integer maximum.

Test cases

[m, n] -> D(m, n)
[5, 8] -> 13073
[5, 7] -> 7183
[3, 9] -> 1159
[8, 6] -> 40081
[8, 8] -> 265729
[1, 7] -> 15
[7, 0] -> 1
[11, 6] -> 227305
[0, 4] -> 1

And all possible outputs for \$0 \le n, m \le 7\$:

[m, n] -> D(m, n)
[0, 0] -> 1
[0, 1] -> 1
[0, 2] -> 1
[0, 3] -> 1
[0, 4] -> 1
[0, 5] -> 1
[0, 6] -> 1
[0, 7] -> 1
[0, 8] -> 1
[1, 0] -> 1
[1, 1] -> 3
[1, 2] -> 5
[1, 3] -> 7
[1, 4] -> 9
[1, 5] -> 11
[1, 6] -> 13
[1, 7] -> 15
[1, 8] -> 17
[2, 0] -> 1
[2, 1] -> 5
[2, 2] -> 13
[2, 3] -> 25
[2, 4] -> 41
[2, 5] -> 61
[2, 6] -> 85
[2, 7] -> 113
[2, 8] -> 145
[3, 0] -> 1
[3, 1] -> 7
[3, 2] -> 25
[3, 3] -> 63
[3, 4] -> 129
[3, 5] -> 231
[3, 6] -> 377
[3, 7] -> 575
[3, 8] -> 833
[4, 0] -> 1
[4, 1] -> 9
[4, 2] -> 41
[4, 3] -> 129
[4, 4] -> 321
[4, 5] -> 681
[4, 6] -> 1289
[4, 7] -> 2241
[4, 8] -> 3649
[5, 0] -> 1
[5, 1] -> 11
[5, 2] -> 61
[5, 3] -> 231
[5, 4] -> 681
[5, 5] -> 1683
[5, 6] -> 3653
[5, 7] -> 7183
[5, 8] -> 13073
[6, 0] -> 1
[6, 1] -> 13
[6, 2] -> 85
[6, 3] -> 377
[6, 4] -> 1289
[6, 5] -> 3653
[6, 6] -> 8989
[6, 7] -> 19825
[6, 8] -> 40081
[7, 0] -> 1
[7, 1] -> 15
[7, 2] -> 113
[7, 3] -> 575
[7, 4] -> 2241
[7, 5] -> 7183
[7, 6] -> 19825
[7, 7] -> 48639
[7, 8] -> 108545
[8, 0] -> 1
[8, 1] -> 17
[8, 2] -> 145
[8, 3] -> 833
[8, 4] -> 3649
[8, 5] -> 13073
[8, 6] -> 40081
[8, 7] -> 108545
[8, 8] -> 265729

Answer 1

Jelly, 8 bytes

Żc@Ɱ,PṚḄ

Try it online!

Because I couldn't tolerate Jelly being tied with APL.

Again uses the formula

$$D(m,n) = \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k$$

but takes m and n as two separate arguments. This is essentially a port of my own Dyalog Extended answer.

Żc@Ɱ,PṚḄ    Dyadic link. Left arg: m, Right arg: n
Ż           Inclusive range 0..m (if m > n, the extra nCk terms will be zero)
    ,       [m, n]
 c@Ɱ        A table containing [[mC0 .. mCk], [nC0 .. nCk]]
     P      Vectorized product; [mC0 * nC0 .. mCk * nCk]
      ṚḄ    Reverse and unbinary; effectively sum mCk * nCk * 2^k for k = 0..m

Alternative 8 bytes, taking a single argument [m, n]:

c€ṂŻ$PṚḄ

Try it online!

Answer 2

APL (Dyalog Unicode), 19 bytes

⊢/(1,2+/+\)⍣⎕⊢1,⎕⍴1

Try it online!

A full program that takes n and m on two separate lines. TIO link has an equivalent dfn for demonstration purposes.

How it works

It goes through the table of Delannoy numbers row by row. Start with the zeroth row of m + 1 ones, and calculate the next row n times:

Previous row: 1 a b c d e ...
Next row:     1 A B C D E ...

From the recurrence relation, we can observe the following:

A = 1 + 1 + a = 2 + a = (1) + (1 + a)
B = A + a + b = 2 + 2a + b = (1 + a) + (1 + a + b)
C = C + b + c = 2 + 2a + 2b + c = (1 + a + b) + (1 + a + b + c)
...

Therefore, we can compute the next row by taking the cumulative sum +\, then pairwise sum 2+/, then prepending a 1. The desired value of D(m,n) is at the end of the row, so we apply ⊢/ at the end.

---

APL (Dyalog Extended), 13 bytes

⊥⍤⌽(×/…⍤⌊!\,)

Try it online!

A straightforward implementation of the Wikipedia formula, also used by multiple other answers.

⊥⍤⌽(×/…⍤⌊!\,)  ⍝ Input: left arg = m, right arg = n
         !\    ⍝ Outer product by nCk function...
      …⍤⌊      ⍝ k = 0..min(n,m)
           ,   ⍝ [m, n]
    ×/         ⍝ Row-wise product; mCk * nCk for each k
⊥⍤⌽            ⍝ Reverse and evaluate in base 2; sum of mCk * nCk * 2^k

Answer 3

Haskell, 37 bytes

m#n|m*n<1=1|i<-m-1,j<-n-1=i#n+m#j+i#j

Try it online!

Straightforward recursive implementation.

Haskell, 41 bytes

0#n=1
m#n|j<-m-1=2*sum(map(j#)[0..n])-j#n

Try it online!

Based on a curious formula I found, but not quite short enough. $$ D(m,n)=2\sum_{k=0}^{n-1}D(m-1,k)+D(m-1,n). $$

Answer 4

J, ^{24 21} 19 bytes

2#.[:*/,!~/],i.@-@]

Try it online!

^{-3 thanks to the base 2 trick from Bubbler's APL answer.}

^{-2 thanks to Bubbler.}

Just this formula translated into J:

$$ D(m,n) = \sum ^ {\min(m, n)} _ {k=0} \binom m k \binom n k 2^k $$

Answer 5

R, 45 bytes

function(m,n,o=0:m,`$`=choose)m$o%*%(n$o*2^o)

Try it online!

Similar but independently-derived approach to pajonk's answer (version 2) - check it out - but here maximizing R's vectorization & vector operators to avoid needing any loop.

Answer 6

Factor + math.combinatorics math.unicode, 65 bytes

[| m n | m n min [0,b] [| k | m k nCk n k nCk k 2^ * * ] map Σ ]

Try it online!

Inputs are re-used so often it's one of the odd times local variables are the terse way to go. Since recursion is generally verbose in Factor, I've gone with the formula

$$D(m,n) = \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k$$

Answer 7

JavaScript (Node.js), 38 bytes

m=>g=n=>m*n?g(n--,m--)+g(n)+g(n,m++):1

Try it online!

Uses the specified formula, so will reach recursion limit on larger testcases.

-1 byte thanks to @dingledooper

-3 bytes thanks to @Arnauld

Answer 8

R, 52 bytes

D=function(x)"if"(all(x),D(x-1:0)+D(x-1)+D(x-0:1),1)

Try it online!

Using the recursive formula and taking input as a tuple (thanks to @Dominic).

Taking input as two arguments:

R, 55 bytes

D=function(m,n)"if"(m*n,D(m-1,n)+D(m-1,n-1)+D(m,n-1),1)

Try it online!

Using the closed-form expression from Wikipedia results in 56 bytes with a loop, but take a look at @Dominic's 45 byte approach!

R, 68 61 58 56 bytes

function(m,n,`$`=choose){for(k in 0:m)F=F+m$k*n$k*2^k;F}

Try it online!

Answer 9

Wolfram Language (Mathematica), 31 bytes

Total//@DiamondMatrix@Table@##&

Try it online!

Returns {1} instead of 1 when the second argument is 0. To fix this, +4 +3 bytes: Try it online!

From Wikipedia:

The Delannoy number \$D(m,n)\$ also counts... the number of cells in an m-dimensional von Neumann neighborhood of radius n...

Generates a matrix representing a radius-m dimension-n von Neumann neighborhood, and counts the number of cells.

---

Some other approaches:

Multinomial formula, 38 36 bytes

Multinomial[k,#-k,#2-k]~Sum~{k,0,#}&

Try it online!

Direct recursion, 46 bytes

f=If[1##>0,f[#-1,#2]+f[#-1,#2-1]+f[#,#2-1],1]&

Try it online!

Generating function, 46 bytes

SeriesCoefficient[1/(2-x y),{x,1,#},{y,1,#2}]&

Try it online!

Answer 10

Python 3, 49 bytes

D=lambda m,n:m*n<1or D(m-1,n)+D(m-1,n-1)+D(m,n-1)

Try it online!

Uses the formula specified in question, and looks like m*n works instead of m and n

-1 byte saved thanks to @CommandMaster forgot that we could use short-circuit evaluation

-4 again for @DingleDooper, genius one line short circuit

Answer 11

Charcoal, 22 bytes

≔Ｅ⊕Ｎ¹θＦＮＵＭθ⁺κ⊗↨…θλ¹Ｉ⊟θ

Try it online! Link is to verbose version of code. Explanation: Uses @Delfad0r's curious formula.

≔Ｅ⊕Ｎ¹θ

Input n and create an array of 1s representing D(0,k) for 0<=k<=n.

ＦＮ

Repeat m times.

ＵＭθ⁺κ⊗↨…θλ¹

Add twice the cumulative sum to each element. (I have to use base 1 conversion because Sum returns None for an empty list. It was still shorter than adding the inclusive and exclusive cumulative sums.)

Ｉ⊟θ

Output D(m,n).

Answer 12

PowerShell Core, 79 67 bytes

filter f($a){if($a*$_){(--$a|f $_)+(--$_|f $a)+($a+1|f $_)}else{1}}

Try it online!

• Saved 1 byte by using a filter
• Saved 3 bytes replacing the -and by a *
• Saved a whopping 12 bytes thanks to Zaelin Goodman

Answer 13

Julia 1.0, 47 30 bytes

m%n=m*n<1||~-m%n+~-m%~-n+m%~-n

Try it online!

Boring port of the formula.

• -12 bytes thanks to @Sisyphus!
• -5 bytes thanks to @MarcMush!

Answer 14

05AB1E, 10 8 bytes

WÝ€cPR2β

Try it online!

-2 thanks to the base 2 trick from Bubbler's APL answer.

Uses the direct formula from wikipedia.

W     push the minimum of m,n
Ý     push the range [0,min(n,m)]
€     and map each number to
 c    the input choose that number, vectorizes
P     product
R     reverse
2β    convert from base 2

Answer 15

Java, 62 bytes

int f(int m,int n){return n*m<1?1:f(m--,n-1)+f(m,n)+f(m,n-1);}

Try it online!

Answer 16

Pari/GP, 45 bytes

d(m,n)=if(m*n,d(m-1,n)+d(m-1,n-1)+d(m,n-1),1)

Try it online!

Answer 17

Ruby, 44 bytes

f=->m,n{m*n<1?1:f[m-1,n]+f[m-1,n-=1]+f[m,n]}

Try it online!

Using the formula in the question

Answer 18

Desmos, 38 bytes

D(m,n)=\sum_{k=0}^mnCr(m,k)nCr(n,k)2^k

Try It On Desmos!

Try It On Desmos! (Prettified)

Implements the formula$$D(m,n)=\sum_{k=0}^{\min(m,n)}\binom mk\binom nk2^k$$with the observation that \$\min(m,n)\$ can be replaced with \$m\$(or \$n\$).

Answer 19

J, 17 bytes

]{(2&+/\@[&0>:$#)

Try it online!

Uses the same algorithm as my 19-byte APL solution. I randomly came across the problem again and realized J has multiple tricks to shorten the code, so it is actually shorter than APL. Also beats Jonah's J solution which uses the direct formula.

Takes m and n as left and right argument respectively.

2&+/ part comes from here.

]{(2&+/\@[&0>:$#)   NB. left arg = m; right arg = n
   xxxxxxxxxyyyy    NB. This part is a hook, so it evaluates as m x (y n)
            >:$#    NB. n+1 copies of 1
   xxxxx@[&0        NB. A trick idiom for "repeat x m times to (y n)"
   2&+/\   NB. Evaluate next row of Delannoy matrix:
       \   NB. For each prefix,
   2&+/    NB. Convert [a, b, ..., m, n] to 2a+2b+...+2m+n
]{         NB. Extract the last element, which is at index n (0-based)

Answer 20

Jelly, 13 bytes

ṂŻc@ⱮµPæ«J$SH

Try it online!

Using the direct formula from Wikipedia.

Ṃ              Minimum
 Ż             [0, 1, ..., min(m, n)]
    Ɱ          For each in the input
  c@           swapped args: input choose k
     P         product (vectorizes)
      æ«J$     bitshift by [1, 2, 3, ...]
          S    sum
           H   halve (since J starts at 1)

Jelly, 14 bytes

_45Bs2¤ß€Sµ1Ȧ?

Try it online!

Could use some work, probably.

             ? If
            Ȧ  all (m != 0, n != 0)
          S    take the sum of
       ß       this link
        €      applied to each of
_              (m, n) -
 45Bs2¤        [1, 0], [1, 1], [0, 1]
 45B           45 as binary: [1, 0, 1, 1, 0, 1]
    s2         sliced into size 2 chunks
           1   Otherwise, 1

Answer 21

Red, 73 bytes

f: func[m n][either(m * n)= 0[1][(f m - 1 n)+(f m - 1 n - 1)+ f m n - 1]]

Try it online!

Uses the formula from the problem description.

Answer 22

MMIX, 64 bytes (16 instrs)

Recursive, so takes forever.

00000000: dc020001 52020003 e3020001 f8030000  ṇ£¡¢R£¡¤ẉ£¡¢ẏ¤¡¡
00000010: fe020004 c1040000 27050101 f303fff9  “£¡¥Ḋ¥¡¡'¦¢¢ṙ¤”ż
00000020: 27060001 f304fff7 c1050100 22030304  '©¡¢ṙ¥”ẋḊ¦¢¡"¤¤¥
00000030: f304fff4 22030304 f6040002 f8040000  ṙ¥”ṡ"¤¤¥ẇ¥¡£ẏ¥¡¡

Disassembled:

delannoy    MOR   $2,$0,$1
            PBNZ  $2,0F
            SETL  $2,1
            POP   3,0           // if(!(m && n)) return(1,m,n)
0H          GET   $2,rJ
            SET   $4,$0
            SUBU  $5,$1,1
            PUSHJ $3,delannoy   // $3,$4,$5 = delannoy(m,n-1) = f(m,n-1),m,n-1
            SUBU  $6,$0,1       // $6 = m - 1
            PUSHJ $4,delannoy   // $4,$5,$6 = delannoy(n-1,m-1)
            SET   $5,$1
            ADDU  $3,$3,$4      // $3 += $4
            PUSHJ $4,delannoy   // $4,$5,$6 = delannoy(n-1,m)
            ADDU  $3,$3,$4
            PUT   rJ,$2
            POP   4,0           // return(f(m,n), m, n)

Answer 23

C (gcc), 45 bytes

D(m,n){m=m*n?D(m-1,n)+D(m-1,n-1)+D(m,n-1):1;}

Try it online!