cp's OEIS Frontend

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

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