A360854 Number of induced cycles in the n X n rook graph.

0, 1, 21, 236, 4040, 114105, 4662721, 256485936, 18226110456, 1623855703785, 177195820502965, 23237493232958796, 3605437233380103056, 653193551573628910481, 136634950180317224879985, 32681589590709963123110080, 8863149183726257535369656976

Offset: 1

Author

Andrew Howroyd, Feb 24 2023

Keywords

• nonn

Comments

Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4). See A070968 for the version that excludes triangles.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• Eric Weisstein's World of Mathematics, Rook Graph.
• Wikipedia, Cycle (graph theory).

Crossrefs

Main diagonal of A360853.

Cf. A070968, A234624, A288961, A360852.

Programs

PARI

a(n) = 2*n*binomial(n,3) + sum(k=2, n, binomial(n,k)^2 * k! * (k-1)!)/2

Formula

a(n) = A288961(n) + A070968(n).

a(n) = 2*n*binomial(n,3) + Sum_{k=2..n} binomial(n,k)^2 * k! * (k-1)! / 2.