A156001 Number of cycles of length 4 in the queen graph associated with an n X n chessboard.

0, 0, 3, 122, 776, 2704, 6987, 15206, 29224, 51680, 85339, 134114, 201792, 293776, 414995, 572558, 772656, 1024320, 1335123, 1716234, 2176728, 2730128, 3387131, 4163830, 5072664, 6132512, 7357675, 8770034, 10385872, 12230288, 14321667

Offset

0,3

Links

Table of n, a(n) for n=0..30.

Eric Weisstein's World of Mathematics, Graph Cycle.

Eric Weisstein's World of Mathematics, Queen Graph.

Index entries for linear recurrences with constant coefficients, signature (3,0,-8,6,6,-8,0,3,-1).

Formula

G.f.: g(x) = x^2*(3+113*x+410*x^2+400*x^3-167*x^4-297*x^5-126*x^6)/((1+x)^3*(1-x)^6).

a(n) = n*(n-1)*(21*n^3+526*n^2-1709*n+996)/60-(3*n^2-12*n+4)*floor(n/2).

Example

For n = 2 the a(2) = 3 cycles are
a1-a2-b2-b1-a1, a1-a2-b1-b2-a1 and a1-b1-a2-b2-a1.
. . . .___. . . . . . . .. . . . . . . . ____ . . .
. . 2 | . | . . . . 2 |\../| . . . . . 2 \../ . . .
. . . | . | . . . . . | \/ | . . . . . . .\/. . . .
. . . | . | . . . . . | /\ | . . . . . . ./\. . . .
. . 1 |___| . . . . 1 |/..\| . . . . . 1 /__\ . . .
. . . a . b . . . . . a .. b . . . . . . a..b . . .

Mathematica

Table[(60 - 1296 n + 3110 n^2 - 2325 n^3 + 505 n^4 + 21 n^5 - 15 (-1)^n (4 - 12 n + 3 n^2))/60, {n, 20}] (* Eric W. Weisstein, Jun 19 2017 *)
LinearRecurrence[{3, 0, -8, 6, 6, -8, 0, 3, -1}, {0, 3, 122, 776, 2704, 6987, 15206, 29224, 51680}, 30] (* Eric W. Weisstein, Jun 19 2017 *)
CoefficientList[Series[-((x (-3 - 113 x - 410 x^2 - 400 x^3 + 167 x^4 + 297 x^5 + 126 x^6))/((-1 + x)^6 (1 + x)^3)), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 19 2017 *)

Prog

(PARI) a(n) = n*(n-1)*(21*n^3+526*n^2-1709*n+996)/60 - n\2*(3*n^2-12*n+4) \\ Charles R Greathouse IV, Jun 19 2017

Crossrefs

Cf. A144298 (3-cycles), A288916 (5-cycles), A288917 (6-cycles).

Sequence in context: A289986 A301559 A141440 * A229633 A171357 A209363

Adjacent sequences: A155998 A155999 A156000 * A156002 A156003 A156004

Keyword

nonn,easy

Author

Anton Voropaev (anton.n.voropaev(AT)gmail.com), Feb 01 2009

Status

approved