OFFSET
1,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1101
FORMULA
From Vaclav Kotesovec, Jul 18 2022: (Start)
Recurrence: (n-4) * (n-2) * (n-1)^2 * (6561*n^8 - 212139*n^7 + 2950263*n^6 - 23053977*n^5 + 110718549*n^4 - 334617561*n^3 + 621301485*n^2 - 647573195*n + 289741950)*a(n) = (n-2) * (98415*n^11 - 3621672*n^10 + 58904658*n^9 - 557565930*n^8 + 3401022330*n^7 - 13968918180*n^6 + 39146085342*n^5 - 74076664722*n^4 + 91284487995*n^3 - 67946473736*n^2 + 26218206060*n-3608592880)*a(n-1) - 2 * (951345*n^11 - 35042301*n^10 + 573945345*n^9 - 5517149841*n^8 + 34570186911*n^7 - 148143645873*n^6 + 442497763659*n^5 - 919659425931*n^4 + 1300075875920*n^3 - 1186236344006*n^2 + 625358201108*n-143083453680)*a(n-2) - 8 * (n-3) * (538002*n^11 - 20170701*n^10 + 335662947*n^9 - 3269686095*n^8 + 20693992482*n^7 - 89239225257*n^6 + 267100420161*n^5 - 553559634623*n^4 + 775814257936*n^3 - 696718449512*n^2 + 358050585284*n-78798884240)*a(n-3) + 64 * (n-4) * (39366*n^11 - 747954*n^10 + 1036638*n^9 + 95287104*n^8 - 1244227635*n^7 + 8077634280*n^6 - 32356061235*n^5 + 84721205046*n^4 - 145611420210*n^3 + 158260316980*n^2 - 98341752748*n + 26435972680)*a(n-4) + 512 * (n-5) * (n-3) * (118098*n^10 - 3864429*n^9 + 55834110*n^8 - 468708363*n^7 + 2528957700*n^6 - 9150957666*n^5 + 22446838206*n^4 - 36764880492*n^3 + 38348031900*n^2 - 22886883656*n + 5886448960)*a(n-5) + 8192 * (n-6) * (n-5) * (n-4) * (n-3) * (6561*n^8 - 159651*n^7 + 1648998*n^6 - 9439902*n^5 + 32737014*n^4 - 70335324*n^3 + 91203060*n^2 - 64949504*n + 19261936)*a(n-6).
a(n) ~ n^2 * 8^(n-1) * (1 - 2*sqrt(6/(Pi*n))). (End)
EXAMPLE
n = 2:
.
Numeration of squares on board:
0 1
2 3
.
By symmetry, the number of routes from each of the 4 starting squares is the same.
.
3 routes starting at square 0:
01 02 03
.
Total number of routes: 4*3 = 12.
---------------------------------
n = 3:
Numeration of squares on board:
0 1 2
3 4 5
6 7 8
.
Using symmetry, only the numbers of routes starting from one of the 4 corner squares (e.g., square 0), one of the 4 side squares (e.g., square 1), and the 1 center square (square 4) need to be considered.
.
18 routes starting at square 0:
010 012 015 014 013
040 041 042 043 045 046 047 048
030 031 034 036 037
.
24 routes starting at square 1:
101 103 104
121 124 125
131 130 134 136 137
141 140 142 143 145 146 147 148
151 152 154 157 158
.
32 routes starting at square 4:
404 401 403
414 410 412 413 415
424 421 425
434 430 431 436 437
454 451 452 457 458
464 463 467
474 473 475 476 478
484 485 487
.
Total number of routes: 4*18 + 4*24 + 1*32 = 72 + 96 + 32 = 200.
MAPLE
b:= proc(n, m, x, y) option remember; `if`(n=0, 1, add(
add((s-> `if`({i, j}={0} or min(s)<1 or max(s)>m, 0,
b(n-1, m, s[])))([x+i, y+j]), j=-1..1), i=-1..1))
end:
a:= n-> add(add(b(n-1, n, x, y), x=1..n), y=1..n):
seq(a(n), n=1..20); # Alois P. Heinz, Jun 20 2022
MATHEMATICA
b[n_, m_, x_, y_] := b[n, m, x, y] = If[n == 0, 1, Sum[Sum[With[{s = {x + i, y + j}}, If[Union@{i, j} == {0} || Min[s] < 1 || Max[s] > m, 0, b[n - 1, m, Sequence @@ s]]], {j, -1, 1}], {i, -1, 1}]];
a[n_] := Sum[Sum[b[n - 1, n, x, y], {x, 1, n}], {y, 1, n}];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 10 2022, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Frank Hollstein, Jun 20 2022
EXTENSIONS
a(11)-a(20) from Alois P. Heinz, Jun 20 2022
STATUS
approved