login
A360854
Number of induced cycles in the n X n rook graph.
3
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
Eric Weisstein's World of Mathematics, Rook Graph.
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.
Sequence in context: A350570 A069601 A173347 * A303968 A304930 A305346
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Feb 24 2023
STATUS
approved