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

0, 1, 9, 60, 250, 765, 1911, 4144, 8100, 14625, 24805, 39996, 61854, 92365, 133875, 189120, 261256, 353889, 471105, 617500, 798210, 1018941, 1285999, 1606320, 1987500, 2437825, 2966301, 3582684, 4297510, 5122125, 6068715, 7150336, 8380944, 9775425, 11349625, 13120380, 15105546, 17324029, 19795815, 22542000

Offset

1,3

Links

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

Eric Weisstein's World of Mathematics, Graph Cycle

Eric Weisstein's World of Mathematics, Rook Graph

Index entries for linear recurrences with constant coefficients, signature (6, -15, 20, -15, 6, -1).

Formula

a(n) = n*binomial(n,2)*(n^2-4*n+5)/2.

a(n) = 6*a(n-1)-15*a(n-2)+20*a(n-3)-15*a(n-4)+6*a(n-5)-a(n-6).

G.f.: (x^2*(1+3*x+21*x^2+5*x^3))/(-1+x)^6.

Mathematica

Table[n^2 (n - 1) (n^2 - 4 n + 5)/4, {n, 20}]
Table[n Binomial[n, 2] (n^2 - 4 n + 5)/2, {n, 20}]
LinearRecurrence[{6, -15, 20, -15, 6, -1}, {0, 1, 9, 60, 250, 765}, 20]
CoefficientList[Series[(x (1 + 3 x + 21 x^2 + 5 x^3))/(-1 + x)^6, {x, 0, 20}], x]

Prog

(Magma) [n^2*(n-1)*(n^2-4*n+5)/4 : n in [1..50]]; // Wesley Ivan Hurt, Apr 23 2021

Crossrefs

Cf. A288961 (3-cycles), A288963 (5-cycles), A288960 (6-cycles).

Sequence in context: A098327 A118674 A268972 * A074431 A268965 A081904

Adjacent sequences: A288959 A288960 A288961 * A288963 A288964 A288965

Keyword

nonn,easy

Author

Eric W. Weisstein, Jun 20 2017

Status

approved