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

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.

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

Prog

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

Crossrefs

Main diagonal of A360851.

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

Sequence in context: A055762 A281714 A236549 * A262732 A220728 A355766

Adjacent sequences: A360849 A360850 A360851 * A360853 A360854 A360855

Keyword

nonn

Author

Andrew Howroyd, Feb 24 2023

Status

approved