|
%I #7 Feb 25 2023 20:57:09
%S 0,1,21,236,4040,114105,4662721,256485936,18226110456,1623855703785,
%T 177195820502965,23237493232958796,3605437233380103056,
%U 653193551573628910481,136634950180317224879985,32681589590709963123110080,8863149183726257535369656976
%N Number of induced cycles in the n X n rook graph.
%C 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.
%H Andrew Howroyd, <a href="/A360854/b360854.txt">Table of n, a(n) for n = 1..100</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">Cycle (graph theory)</a>.
%F a(n) = A288961(n) + A070968(n).
%F a(n) = 2*n*binomial(n,3) + Sum_{k=2..n} binomial(n,k)^2 * k! * (k-1)! / 2.
%o (PARI) a(n) = 2*n*binomial(n,3) + sum(k=2, n, binomial(n,k)^2 * k! * (k-1)!)/2
%Y Main diagonal of A360853.
%Y Cf. A070968, A234624, A288961, A360852.
%K nonn
%O 1,3
%A _Andrew Howroyd_, Feb 24 2023
| 