# 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? – Bubbler May 7 at 4:29 • @Bubbler I'm going to say no, as the sequence is specifically designed for 0 based inputs – caird coinheringaahing May 7 at 4:30 • These look a lot like Motzkin numbers. – xnor May 7 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 – caird coinheringaahing May 7 at 5:03 • I love these diagrams. Thanks for the challenge! – Eric Duminil May 8 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 – hyper-neutrino May 7 at 5:28 • Clever use of Ḅ for $2^k$, +1! – caird coinheringaahing May 7 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. – Jonah May 7 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)$? – Giuseppe May 7 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 ;) – Delfad0r May 7 at 20:55
• Oh! I see, wasn't sure how [0..n] worked, thanks! – Giuseppe May 7 at 20:56

# 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$$ # 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. – Bubbler May 7 at 5:57 • Meaning I can assume they are ordered? – Jonah May 7 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+<. – Bubbler May 7 at 6:40 # 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? – dingledooper May 7 at 4:38 • @dingledooper I don't think so. – A username May 7 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 – hyper-neutrino May 7 at 4:49 • I don't think that m&n works (e.g. 5&2=0). m*n does though. – dingledooper May 7 at 4:56 • 38 bytes by taking (m)(n) and doing the recursion on the inner function. – Arnauld May 7 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. – Dominic van Essen May 7 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!) – Dominic van Essen May 7 at 12:30
• @DominicvanEssen I think your solutions are distinct enough to be posted separately. Clever use of %*%! Also for the recursion: -1 byte – pajonk May 7 at 12:47
• Ok - I posted my version of the choose one, but the recursive one is definitely yours! – Dominic van Essen May 7 at 16:32

# 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 – Command Master May 7 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). – dingledooper May 7 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! – Zaelin Goodman May 7 at 13:29 • -7 additional bytes by putting the parameter outside the block, shuffling some parameters, and eliminating more unneeded parenthesis Try it online! – Zaelin Goodman May 7 at 14:39 • -1 additional byte (sorry, just missed my editing window) by shuffling parameters again Try it online! – Zaelin Goodman May 7 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} – Zaelin Goodman May 7 at 15:56

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

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

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

# 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! – Sisyphus May 8 at 6:21
• save 5 more bytes by using || Try it online! – MarcMush May 8 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. – sporklpony May 14 at 23:36
• @MarcMush Thank you, I wasn't aware that false and true were treated as 0 and 1 in Julia! – sporklpony May 14 at 23:36

# 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! – caird coinheringaahing May 7 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 – hyper-neutrino May 7 at 4:39 # 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. # 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!

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