A360200 Number of induced paths in the n X n grid graph.

0, 8, 94, 1004, 14864, 334536, 11546874, 629381852, 56094263348, 8343512638896, 2074276200162230, 853966325494701152, 578432462293854136504, 646135466408339553958096, 1200595044818176185884236342

Offset

1,2

Comments

Paths of length zero are not counted here.

Equivalently, a(n) is the number of snake-like polyominoes in an n X n square. Rotations, reflections and translations are counted separately.

Links

Table of n, a(n) for n=1..15.

Eric Weisstein's World of Mathematics, Grid Graph

Wikipedia, Induced path

Example

The a(2) = 8 induced paths are:
  O O   O .   . .   . O   O O   O .   . O   O O
  . .   O .   O O   . O   O .   O O   O O   . O

Crossrefs

Main diagonal of A360199.

Cf. A059525, A297664 (induced cycles), A331968, A331986 (of maximum length), A357516.

Sequence in context: A299846 A214385 A121161 * A098269 A010565 A299002

Adjacent sequences: A360197 A360198 A360199 * A360201 A360202 A360203

Keyword

nonn,more

Author

Andrew Howroyd, Jan 29 2023

Status

approved