A288967 -id:A288967 - cp's OEIS frontend

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

Andrew Howroyd, Feb 24 2023

nonn

Paths of length zero are not counted here.

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

Main diagonal of A360851.

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

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

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

A360877 Array read by antidiagonals: T(m,n) is the number of (undirected) paths in the rook graph K_m X K_n.

Original entry on oeis.org

0, 1, 1, 6, 12, 6, 30, 129, 129, 30, 160, 1984, 4536, 1984, 160, 975, 45945, 310542, 310542, 45945, 975, 6846, 1524156, 38298270, 111933456, 38298270, 1524156, 6846

Offset: 1

Andrew Howroyd, Feb 25 2023

			Array begins:
==============================================
m\n|   1     2        3         4        5 ...
---+------------------------------------------
1  |   0     1        6        30      160 ...
2  |   1    12      129      1984    45945 ...
3  |   6   129     4536    310542 38298270 ...
4  |  30  1984   310542 111933456 ...
5  | 160 45945 38298270 ...
  ...

Eric Weisstein's World of Mathematics, Graph Path.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A288967.
Rows 1..2 are A038155, A360878.
Cf. A269562, A269565, A286418, A360851, A360855.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula