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,3

Links

Table of n, a(n) for n=1..27.

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).

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).

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]

Crossrefs

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

Sequence in context: A354692 A373882 A347844 * A074731 A064560 A264121

Adjacent sequences: A291907 A291908 A291909 * A291911 A291912 A291913

Keyword

nonn,changed

Author

Eric W. Weisstein, Sep 05 2017

Status

approved