login
Number of induced paths in the n X n rook graph.
3

%I #9 Feb 25 2023 20:57:06

%S 0,8,126,2208,55700,2006280,98309778,6291829376,509638185288,

%T 50963818537800,6166622043087110,887993574204562848,

%U 150070914040571147676,29413899151951944980168,6618127309189187620585050,1694240591152432030869834240,489635530843052856921382173968

%N Number of induced paths in the n X n rook graph.

%C Paths of length zero are not counted here.

%H Andrew Howroyd, <a href="/A360852/b360852.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/Induced_path">Induced path</a>.

%F a(n) = -n^2 + n!^2 * Sum_{k=0..n-1} (1 + k)/(k!^2).

%F a(n) = A288035(n) - n^2 = A288035(n) - A000290(n).

%o (PARI) a(n) = {sum(k=0, n-1, n!^2*(1 + k)/(k!^2)) - n^2}

%Y Main diagonal of A360851.

%Y Cf. A000290, A286189 (induced connected subgraphs), A288035, A288967.

%K nonn

%O 1,2

%A _Andrew Howroyd_, Feb 24 2023