A061593 Number of ways to place 2n nonattacking kings on a 4 X 2n chessboard.

12, 79, 408, 1847, 7698, 30319, 114606, 419933, 1501674, 5266069, 18174084, 61892669, 208424880, 695179339, 2299608732, 7552444115, 24648046806, 79994460139, 258339007890, 830619734681, 2660070154542, 8488515938929, 27000079296648, 85629004867577

Offset: 1

Author

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001

Keywords

• nonn
• easy
• nice

Links

• Bruno Berselli, Table of n, a(n) for n = 1..200
• D. E. Knuth, Nonattacking kings on a chessboard, 1994.
• Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 90.
• H. S. Wilf, The problem of the kings, Elec. J. Combin. 2, 1995.
• Index entries for linear recurrences with constant coefficients, signature (9,-28,33,-9).

Crossrefs

Column k=2 of A350819.

Cf. A061594, A001787.

Programs

Magma

[(17*n-109)*3^n+2*Fibonacci(2*n+10): n in [1..30]]; // Vincenzo Librandi, Jul 12 2011

Maple

with(combinat): A061593:=n->(17*n-109)*3^n+2*fibonacci(2*n+10): seq(A061593(n), n=1..30); # Wesley Ivan Hurt, Nov 08 2014

Mathematica

Table[(17 n - 109)*3^n + 2 Fibonacci[2 n + 10], {n, 30}] (* Wesley Ivan Hurt, Nov 08 2014 *)
CoefficientList[Series[x (12-29x+33x^2-9x^3)/((1-3x+x^2)(1-3x)^2),{x,0,30}],x] (* or *) LinearRecurrence[{9,-28,33,-9},{0,12,79,408,1847},30] (* Harvey P. Dale, Dec 20 2021 *)

Formula

G.f.: x*(12-29*x+33*x^2-9*x^3)/((1-3*x+x^2)*(1-3*x)^2).

a(n) = 9*a(n-1) - 28*a(n-2) + 33*a(n-3) - 9*a(n-4); a(1)=12, a(2)=79, a(3)=408, a(4)=1847.

a(n) = (17*n-109)*3^n + 2*Fibonacci(2*n+10).

a(n) = 17*A027471(n+2) - 126*A000244(n) + A025169(n+4).