A355127 a(n) is the number of different (n-1)-move routes for a king on an empty n X n chessboard.
1, 12, 200, 2880, 37680, 455224, 5186888, 56471040, 593296160, 6057160296, 60407414256, 590807590672, 5684125083000, 53924502344880, 505415790232592, 4687367714152128, 43070861665247616, 392532002390446600, 3551337773634149120, 31920035670120464496
Offset: 1
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..1101
Programs
-
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 *)
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)
Extensions
a(11)-a(20) from Alois P. Heinz, Jun 20 2022