login
A156001
Number of cycles of length 4 in the queen graph associated with an n X n chessboard.
3
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
Eric Weisstein's World of Mathematics, Graph Cycle.
Eric Weisstein's World of Mathematics, Queen Graph.
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
KEYWORD
nonn,easy
AUTHOR
Anton Voropaev (anton.n.voropaev(AT)gmail.com), Feb 01 2009
STATUS
approved