login
a(n) is the number of different (n-1)-move routes for a king on an empty n X n chessboard.
2

%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