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

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

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.

Prog

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

Crossrefs

Main diagonal of A360853.

Cf. A070968, A234624, A288961, A360852.

Sequence in context: A350570 A069601 A173347 * A303968 A304930 A305346

Adjacent sequences: A360851 A360852 A360853 * A360855 A360856 A360857

Keyword

nonn

Author

Andrew Howroyd, Feb 24 2023

Status

approved