17
\$\begingroup\$

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:

enter image description here

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
\$\endgroup\$
5
  • \$\begingroup\$ May I take m and n as 1-based? \$\endgroup\$ – Bubbler May 7 at 4:29
  • 1
    \$\begingroup\$ @Bubbler I'm going to say no, as the sequence is specifically designed for 0 based inputs \$\endgroup\$ – caird coinheringaahing May 7 at 4:30
  • \$\begingroup\$ These look a lot like Motzkin numbers. \$\endgroup\$ – xnor May 7 at 5:01
  • \$\begingroup\$ @xnor They are a similar/related sequence, but I don't think the answers are similar enough for these to be duplicates \$\endgroup\$ – caird coinheringaahing May 7 at 5:03
  • 1
    \$\begingroup\$ I love these diagrams. Thanks for the challenge! \$\endgroup\$ – Eric Duminil May 8 at 10:52

23 Answers 23

10
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ oh, I didn't even think about what xCk terms for x>min would turn out as, lol. That unbinary trick is genius tho \$\endgroup\$ – hyper-neutrino May 7 at 5:28
  • 1
    \$\begingroup\$ Clever use of for \$2^k\$, +1! \$\endgroup\$ – caird coinheringaahing May 7 at 5:28
8
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Oh, nice base 2 trick. I'm going to try that in my answer. \$\endgroup\$ – Jonah May 7 at 5:04
6
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Should your formula be \$-D(m-1,n)\$? \$\endgroup\$ – Giuseppe May 7 at 20:33
  • \$\begingroup\$ @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 ;) \$\endgroup\$ – Delfad0r May 7 at 20:55
  • \$\begingroup\$ Oh! I see, wasn't sure how [0..n] worked, thanks! \$\endgroup\$ – Giuseppe May 7 at 20:56
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ You don't need to explicitly take the minimum of m and n. \$\endgroup\$ – Bubbler May 7 at 5:57
  • \$\begingroup\$ Meaning I can assume they are ordered? \$\endgroup\$ – Jonah May 7 at 6:38
  • 1
    \$\begingroup\$ 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+<. \$\endgroup\$ – Bubbler May 7 at 6:40
4
\$\begingroup\$

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

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Does m*n work? \$\endgroup\$ – dingledooper May 7 at 4:38
  • \$\begingroup\$ @dingledooper I don't think so. \$\endgroup\$ – A username May 7 at 4:40
  • \$\begingroup\$ It works from what I can tell; tested a few cases though not all of them. might overflow but that should be fine anyway \$\endgroup\$ – hyper-neutrino May 7 at 4:49
  • 1
    \$\begingroup\$ I don't think that m&n works (e.g. 5&2=0). m*n does though. \$\endgroup\$ – dingledooper May 7 at 4:56
  • 3
    \$\begingroup\$ 38 bytes by taking (m)(n) and doing the recursion on the inner function. \$\endgroup\$ – Arnauld May 7 at 7:01
4
\$\begingroup\$

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!

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

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Command Master May 7 at 4:57
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – dingledooper May 7 at 5:00
3
\$\begingroup\$

Charcoal, 22 bytes

≔E⊕N¹θFNUMθ⁺κ⊗↨…θλ¹I⊟θ

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

≔E⊕N¹θ

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

FN

Repeat m times.

UMθ⁺κ⊗↨…θλ¹

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

I⊟θ

Output D(m,n).

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ -4 bytes by cutting one set of unnecessary parenthesis and using -- to save a single -1 . Try it online! \$\endgroup\$ – Zaelin Goodman May 7 at 13:29
  • 1
    \$\begingroup\$ -7 additional bytes by putting the parameter outside the block, shuffling some parameters, and eliminating more unneeded parenthesis Try it online! \$\endgroup\$ – Zaelin Goodman May 7 at 14:39
  • 1
    \$\begingroup\$ -1 additional byte (sorry, just missed my editing window) by shuffling parameters again Try it online! \$\endgroup\$ – Zaelin Goodman May 7 at 14:47
  • 2
    \$\begingroup\$ 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} \$\endgroup\$ – Zaelin Goodman May 7 at 15:56
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I like the 45Bs2¤. I had a naive 18 bytes: Try it online! \$\endgroup\$ – caird coinheringaahing May 7 at 4:37
  • \$\begingroup\$ @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 \$\endgroup\$ – hyper-neutrino May 7 at 4:39
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.