|
%I #12 Mar 04 2024 21:29:47
%S 0,0,3,122,776,2704,6987,15206,29224,51680,85339,134114,201792,293776,
%T 414995,572558,772656,1024320,1335123,1716234,2176728,2730128,3387131,
%U 4163830,5072664,6132512,7357675,8770034,10385872,12230288,14321667
%N Number of cycles of length 4 in the queen graph associated with an n X n chessboard.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-8,6,6,-8,0,3,-1).
%F 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).
%F a(n) = n*(n-1)*(21*n^3+526*n^2-1709*n+996)/60-(3*n^2-12*n+4)*floor(n/2).
%e For n = 2 the a(2) = 3 cycles are
%e a1-a2-b2-b1-a1, a1-a2-b1-b2-a1 and a1-b1-a2-b2-a1.
%e . . . .___. . . . . . . .. . . . . . . . ____ . . .
%e . . 2 | . | . . . . 2 |\../| . . . . . 2 \../ . . .
%e . . . | . | . . . . . | \/ | . . . . . . .\/. . . .
%e . . . | . | . . . . . | /\ | . . . . . . ./\. . . .
%e . . 1 |___| . . . . 1 |/..\| . . . . . 1 /__\ . . .
%e . . . a . b . . . . . a .. b . . . . . . a..b . . .
%t 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 *)
%t 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 *)
%t 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 *)
%o (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
%Y Cf. A144298 (3-cycles), A288916 (5-cycles), A288917 (6-cycles).
%K nonn,easy
%O 0,3
%A Anton Voropaev (anton.n.voropaev(AT)gmail.com), Feb 01 2009
|
