# Counting Queen's paths on a rectangular chessboard

Given two positive integers $$\m,n\$$, imagine a chessboard of size $$\m \times n\$$. A chess queen is on the upper-left corner. In how many ways can it reach the lower-right corner, by moving only right, down, or diagonally right-down (possibly moving many steps at once, because it's a queen)?

The resulting 2D sequence is A132439.

Standard rules apply. The shortest code in bytes wins.

## Test cases

m n result
1 1      1
1 2      1
1 3      2
1 4      4
1 5      8
2 2      3
2 3      7
2 4     17
2 5     40
3 3     22
3 4     60
3 5    158
4 4    188
4 5    543
5 5   1712


1!1=1;m!n=sum[m!(n-x)+(m-x)!n+(m-x)!(n-x)|x<-[1..m+n]]


Try it online!

Initially a boring port of the comment on OEIS

-27 from some tricks off dingledooper's answer

-10 from Christian Sievers

• I think you can replace max m n with m+n – Christian Sievers Apr 13 at 8:45
• @ChristianSievers seems like it, and with that the m*n>0 check was also unnecessary, ty! – clapp Apr 13 at 9:02

# Python 2, 75 bytes

@xnor's idea which is 2 bytes smaller than the one below. Returns True for 1 1.

f=lambda m,n:sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n|m))or m>0<n


Try it online!

# Python 2, 79 77 bytes

f=lambda m,n:(m==n==1)+sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n+m))


Try it online!

• I think the 77-byter is surely correct. The correctness is clear and it will end in finite time because n+m is decreasing. – newbie Apr 13 at 3:59
• Yes, you're definitely right. It probably just takes longer for larger inputs. – dingledooper Apr 13 at 17:52
• Here's a way to shave two bytes off the base case for the first one, with True for 1: Try it online! – xnor Apr 13 at 21:36
• @xnor Clever idea; thanks for the improvement! – dingledooper Apr 13 at 21:48

# K (ngn/k), 33 bytes

{(x~1 1)+/o'x-/:{|/~x,-/x}#1_+!x}


Try it online!

!x odometer

+ transpose

1_ drop the first

{ }# filter

|/~x,-/x either element or their difference is 0

x-/: subtract each right

o' recur each

+/ sum

(x~1 1) does x match 1 1? use as initial value for the sum

# Erlang (escript), 92 bytes

f(1,1)->1;f(M,N)->lists:sum([f(M,N-X)+f(M-X,N)+f(M-X,N-X)||X<-lists:seq(1,max(M,N)),M*N>0]).


Try it online!

# Charcoal, 40 bytes

ＮθＦＮＦθ⊞υ∨¬υΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθＩ⊟υ


Try it online! Link is to verbose version of code. Explanation:

Ｎθ


Input the number of columns.

ＦＮ


Loop over the rows.

Ｆθ


Loop over each column.

⊞υ∨¬υ


The first result is always 1...

ΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθ


... otherwise find the existing results that are a Queen's move away, take the total, and push that to the list of results. The list therefore simulates a matrix, requiring its index to be divided or taken modulo the number of columns as appropriate to compare with the loop variables.

Ｉ⊟υ


Output the last result calculated.

# J, 60 50 bytes

_2{(],1#.]#~(#:#)(0=*/*-/)@:-"1(#:i.@#))^:(*/@[)&1


Try it online!