A094895 Sequence generated from a Knight's tour of a 4 X 4 chessboard considered as a matrix.

1, 280, 8524, 295840, 10014256, 340831360, 11585508544, 393929320960, 13393420731136, 455377714186240, 15482831007960064, 526416344465121280, 17898154990259286016, 608537275441252433920, 20690267318823093059584

Offset: 1

Author

Gary W. Adamson, Jun 13 2004

Keywords

• nonn
• easy

Comments

The 4 X 4 chessboard format is a Knight's tour (inclusive of the integers 1-16) as shown on p. 76 of Watkins, which he generated from the Gray code. a(n)/a(n-1) tends to 34, an eigenvalue of the characteristic polynomial of the matrix: x^4 - 24x^3 - 324x^2 - 544x. The recursion multipliers (24), (324) and (544) may be seen with changed signs as the 3 rightmost coefficients of the characteristic polynomial.

Examples

			a(3) = 8524, leftmost term of M^3 * [1 0 0 0]: [8524, 8816, 8780, 8560].
a(5) = 10014256 = 24*295840 + 324*8524 + 544*280.
		

References

• John J. Watkins, "Across the Board, The Mathematics of Chessboard Problems" Princeton University Press, 2004, p. 76.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..650
• Index entries for linear recurrences with constant coefficients, signature (24,324,544).

Programs

GAP

List([1..20], n-> 2^(n-2)*((-4)^n + 9*(-1)^n + 15*17^(n-1))); # G. C. Greubel, Jul 11 2019

Magma

[2^(n-2)*((-4)^n + 9*(-1)^n + 15*17^(n-1)): n in [1..20]]; // G. C. Greubel, Jul 11 2019

Mathematica

a[n_] := (MatrixPower[{{1, 6, 15, 12}, {14, 9, 4, 7}, {5, 2, 11, 16}, {10, 13, 8, 3}}, n].{{1}, {0}, {0}, {0}})[[1, 1]]; Table[ a[n], {n, 20}] (* Robert G. Wilson v, Jun 16 2004 *)
Table[2^(n-2)*((-4)^n + 9*(-1)^n + 15*17^(n-1)), {n,20}] (* G. C. Greubel, Jul 11 2019 *)

PARI

vector(20, n, 2^(n-2)*((-4)^n + 9*(-1)^n + 15*17^(n-1))) \\ G. C. Greubel, Jul 11 2019

Sage

[2^(n-2)*((-4)^n + 9*(-1)^n + 15*17^(n-1)) for n in (1..20)] # G. C. Greubel, Jul 11 2019

Formula

Begin with the 4 X 4 matrix M = [1 6 15 12 / 14 9 4 7 / 5 2 11 16 / 10 13 8 3]. Then a(n) = leftmost term in M^n * [1 0 0 0]. Recursion method: a(n+3) = 24*a(n+2) + 324*a(n+1) + 544*a(n); n>4.

From Colin Barker, Oct 21 2012: (Start)

a(n) = 2^(n-2)*(17*(-4)^n + 153*(-1)^n + 15*17^n)/17.

G.f.: x*(1 +256*x +1480*x^2)/((1+2*x)*(1+8*x)*(1-34*x)). (End)

Extensions

Edited and extended by Robert G. Wilson v, Jun 16 2004