%I #56 Sep 11 2022 00:48:03
%S 1,12,200,2880,37680,455224,5186888,56471040,593296160,6057160296,
%T 60407414256,590807590672,5684125083000,53924502344880,
%U 505415790232592,4687367714152128,43070861665247616,392532002390446600,3551337773634149120,31920035670120464496
%N a(n) is the number of different (n-1)-move routes for a king on an empty n X n chessboard.
%H Alois P. Heinz, <a href="/A355127/b355127.txt">Table of n, a(n) for n = 1..1101</a>
%F From _Vaclav Kotesovec_, Jul 18 2022: (Start)
%F 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).
%F a(n) ~ n^2 * 8^(n-1) * (1 - 2*sqrt(6/(Pi*n))). (End)
%e n = 2:
%e .
%e Numeration of squares on board:
%e 0 1
%e 2 3
%e .
%e By symmetry, the number of routes from each of the 4 starting squares is the same.
%e .
%e 3 routes starting at square 0:
%e 01 02 03
%e .
%e Total number of routes: 4*3 = 12.
%e ---------------------------------
%e n = 3:
%e Numeration of squares on board:
%e 0 1 2
%e 3 4 5
%e 6 7 8
%e .
%e 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.
%e .
%e 18 routes starting at square 0:
%e 010 012 015 014 013
%e 040 041 042 043 045 046 047 048
%e 030 031 034 036 037
%e .
%e 24 routes starting at square 1:
%e 101 103 104
%e 121 124 125
%e 131 130 134 136 137
%e 141 140 142 143 145 146 147 148
%e 151 152 154 157 158
%e .
%e 32 routes starting at square 4:
%e 404 401 403
%e 414 410 412 413 415
%e 424 421 425
%e 434 430 431 436 437
%e 454 451 452 457 458
%e 464 463 467
%e 474 473 475 476 478
%e 484 485 487
%e .
%e Total number of routes: 4*18 + 4*24 + 1*32 = 72 + 96 + 32 = 200.
%p b:= proc(n, m, x, y) option remember; `if`(n=0, 1, add(
%p add((s-> `if`({i, j}={0} or min(s)<1 or max(s)>m, 0,
%p b(n-1, m, s[])))([x+i, y+j]), j=-1..1), i=-1..1))
%p end:
%p a:= n-> add(add(b(n-1, n, x, y), x=1..n), y=1..n):
%p seq(a(n), n=1..20); # _Alois P. Heinz_, Jun 20 2022
%t 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}]];
%t a[n_] := Sum[Sum[b[n - 1, n, x, y], {x, 1, n}], {y, 1, n}];
%t Table[a[n], {n, 1, 20}] (* _Jean-François Alcover_, Sep 10 2022, after _Alois P. Heinz_ *)
%Y Cf. A086346, A086347, A151331, A323562.
%K nonn,walk
%O 1,2
%A _Frank Hollstein_, Jun 20 2022
%E a(11)-a(20) from _Alois P. Heinz_, Jun 20 2022