A361185 Number of chordless cycles in the n X n rook complement graph.

0, 0, 15, 264, 1700, 6900, 21315, 54880, 123984, 253800, 480975, 856680, 1450020, 2351804, 3678675, 5577600, 8230720, 11860560, 16735599, 23176200, 31560900, 42333060, 56007875, 73179744, 94530000, 120835000, 152974575, 191940840, 238847364, 294938700

Offset: 1

Author

Eric W. Weisstein, Mar 03 2023

Keywords

• nonn

Comments

Using the convention that chordless cycles have length >= 4.

All chordless cycles in the rook complement graph have a cycle length of either 4 or 6. - Andrew Howroyd, Mar 03 2023

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Chordless Cycle
• Eric Weisstein's World of Mathematics, Rook Complement Graph
• Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Crossrefs

Cf. A070968, A360854.

Programs

Mathematica

Table[(n - 2) (n - 1)^2 n^2 (6 n - 13)/12, {n, 20}]
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 0, 15, 264, 1700, 6900, 21315}, 20]
CoefficientList[Series[x^2 (15 + 159 x + 167 x^2 + 19 x^3)/(1 - x)^7, {x, 0, 20}], x]

PARI

a(n) = 2*binomial(n,2)*binomial(n,3) + 9*binomial(n,3)^2 + 12*binomial(n,4)*binomial(n,2) \\ Andrew Howroyd, Mar 03 2023

Formula

a(n) = 2*binomial(n,2)*binomial(n,3) + 9*binomial(n,3)^2 + 12*binomial(n,4)*binomial(n,2). - Andrew Howroyd, Mar 03 2023

a(n) = (n - 2)*(n - 1)^2*n^2*(6*n - 13)/12.

a(n) = 7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7).

G.f.: x^3*(15+159*x+167*x^2+19*x^3)/(1-x)^7.

Extensions

Terms a(8) and beyond from Andrew Howroyd, Mar 03 2023