A291910 Number of 4-cycles in the n X n rook complement graph.

0, 0, 9, 576, 6900, 44100, 196245, 686784, 2023056, 5232600, 12224025, 26310240, 52936884, 100663836, 182452725, 317318400, 532407360, 865571184, 1368508041, 2110550400, 3183182100, 4705372980, 6829824309, 9750223296, 13709610000, 19009965000, 26023131225

Offset: 1

Author

Eric W. Weisstein, Sep 05 2017

Keywords

• nonn

Links

• Eric Weisstein's World of Mathematics, Graph Cycle
• Eric Weisstein's World of Mathematics, Rook Complement Graph
• Index entries for linear recurrences with constant coefficients, signature (9, -36, 84, -126, 126, -84, 36, -9, 1).

Crossrefs

Cf. A179058 (3-cycles), A291911 (5-cycles), A291912 (6-cycles).

Programs

Mathematica

Table[(-2 + n) (-1 + n)^2 n^2 (-4 + 5 n - 4 n^2 + n^3)/8, {n, 20}]
LinearRecurrence[{9, -36, 84, -126, 126, -84, 36, -9, 1}, {0, 0, 9, 576, 6900, 44100, 196245, 686784, 2023056}, 30]
CoefficientList[Series[-((3 x^2 (3 + 165 x + 680 x^2 + 660 x^3 + 165 x^4 + 7 x^5))/(-1 + x)^9), {x, 0, 20}], x]

Formula

a(n) = (n-2)*(n-1)^2*n^2*(-4 + 5*n - 4*n^2 + n^3)/8.

a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9).

G.f.: -((3 x^3 (3 + 165 x + 680 x^2 + 660 x^3 + 165 x^4 + 7 x^5))/(-1 + x)^9).