A360852 Number of induced paths in the n X n rook graph.

0, 8, 126, 2208, 55700, 2006280, 98309778, 6291829376, 509638185288, 50963818537800, 6166622043087110, 887993574204562848, 150070914040571147676, 29413899151951944980168, 6618127309189187620585050, 1694240591152432030869834240, 489635530843052856921382173968

Offset: 1

Author

Andrew Howroyd, Feb 24 2023

Keywords

• nonn

Comments

Paths of length zero are not counted here.

Links

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

Crossrefs

Main diagonal of A360851.

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

Programs

PARI

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

Formula

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

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