# Delannoy numbers

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 , 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  • May I take m and n as 1-based? May 7, 2021 at 4:29 • @Bubbler I'm going to say no, as the sequence is specifically designed for 0 based inputs May 7, 2021 at 4:30 • These look a lot like Motzkin numbers. – xnor May 7, 2021 at 5:01 • @xnor They are a similar/related sequence, but I don't think the answers are similar enough for these to be duplicates May 7, 2021 at 5:03 • I love these diagrams. Thanks for the challenge! May 8, 2021 at 10:52 ## 23 Answers # 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! • oh, I didn't even think about what xCk terms for x>min would turn out as, lol. That unbinary trick is genius tho May 7, 2021 at 5:28 • Clever use of Ḅ for $2^k$, +1! May 7, 2021 at 5:28 # 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

• Oh, nice base 2 trick. I'm going to try that in my answer. May 7, 2021 at 5:04

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


Try it online!

Straightforward recursive implementation.

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).$$

• Should your formula be $-D(m-1,n)$? May 7, 2021 at 20:33
• @Giuseppe No I think it's right, because $k$ ranges from $0$ to $n-1$ in the sum. In the code I actually sum for $k=0$ to $n$ and then subtract $D(m-1,n)$ because, you know, bytes ;) May 7, 2021 at 20:55
• Oh! I see, wasn't sure how [0..n] worked, thanks! May 7, 2021 at 20:56

# 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$$

• You don't need to explicitly take the minimum of m and n. May 7, 2021 at 5:57
• Meaning I can assume they are ordered? May 7, 2021 at 6:38
• Not that, but the values of k higher than min(m,n) will be silently ignored because one of the nCks become 0. So you can do something like ],i.@-@] instead of [:i.@-1+<. May 7, 2021 at 6:40

# 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. # 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$$ # 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 • Does m*n work? May 7, 2021 at 4:38 • @dingledooper I don't think so. May 7, 2021 at 4:40 • It works from what I can tell; tested a few cases though not all of them. might overflow but that should be fine anyway May 7, 2021 at 4:49 • I don't think that m&n works (e.g. 5&2=0). m*n does though. May 7, 2021 at 4:56 • 38 bytes by taking (m)(n) and doing the recursion on the inner function. May 7, 2021 at 7:01 # 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, 686158 56 bytes function(m,n,$=choose){for(k in 0:m)F=F+m$k*n$k*2^k;F}


Try it online!

• 53 bytes by accepting m,n as 2-element vector. May 7, 2021 at 12:20
• (I was thinking all morning about how to use choose, and came up with this... only to find you'd beaten me to it!) May 7, 2021 at 12:30
• @DominicvanEssen I think your solutions are distinct enough to be posted separately. Clever use of %*%! Also for the recursion: -1 byte May 7, 2021 at 12:47
• Ok - I posted my version of the choose one, but the recursive one is definitely yours! May 7, 2021 at 16:32

# 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!

# 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

• D=lambda m,n:m*n and D(m-1,n)+D(m-1,n-1)+D(m,n-1)or 1 is 53 bytes May 7, 2021 at 4:57
• D=lambda m,n:m*n<1or D(m-1,n)+D(m-1,n-1)+D(m,n-1) is 49 (or you can replace m*n<1 with 1>>m*n if you don't like that True is outputted in place of 1). May 7, 2021 at 5:00

# 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).

# 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 • -4 bytes by cutting one set of unnecessary parenthesis and using -- to save a single -1 . Try it online! May 7, 2021 at 13:29 • -7 additional bytes by putting the parameter outside the block, shuffling some parameters, and eliminating more unneeded parenthesis Try it online! May 7, 2021 at 14:39 • -1 additional byte (sorry, just missed my editing window) by shuffling parameters again Try it online! May 7, 2021 at 14:47 • You can save another 9 bytes (down to 58) by switching to PS7 and using the ternary operator, but then you lose the nice TIO support: filter f($a){$a*$_ ?(--$a|f$_)+(--$_|f$a)+($a+1|f$_):1} May 7, 2021 at 15:56

# 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!
• Save 12 bytes by redefining %: Try it online! May 8, 2021 at 6:21
• save 5 more bytes by using || Try it online! May 8, 2021 at 12:07
• @Sisyphus Thank you! New to Julia, didn't realize operators could be redefined that easily. Also nice trick with the bitwise not, that's definitely something I'll need to keep in mind. May 14, 2021 at 23:36
• @MarcMush Thank you, I wasn't aware that false and true were treated as 0 and 1 in Julia! May 14, 2021 at 23:36

# 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


# 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!

# 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!

# 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

# 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\$$).

# 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)  # 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  • I like the 45Bs2¤. I had a naive 18 bytes: Try it online! May 7, 2021 at 4:37 • @cairdcoinheringaahing Oh, I see. I didn't want to deal with calling on the chain that many times, lmao. Felt it'd be easier to take as pairs and then just generate the neighborhood May 7, 2021 at 4:39 # Red, 73 bytes f: func[m n][either(m * n)= 0[(f m - 1 n)+(f m - 1 n - 1)+ f m n - 1]]  Try it online! Uses the formula from the problem description. # 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)


# 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!