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

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

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.

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]

Prog

(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

Crossrefs

Cf. A070968, A360854.

Sequence in context: A206230 A209263 A180832 * A013381 A013384 A013380

Adjacent sequences: A361182 A361183 A361184 * A361186 A361187 A361188

Keyword

nonn

Author

Eric W. Weisstein, Mar 03 2023

Extensions

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

Status

approved