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

Author

Andrew Howroyd, Jan 29 2023

Keywords

• nonn
• more

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.

Examples

			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
		

Links

• Eric Weisstein's World of Mathematics, Grid Graph
• Wikipedia, Induced path

Crossrefs

Main diagonal of A360199.

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