login
Number of induced paths in the n X n grid graph.
3

%I #9 Jan 29 2023 23:01:37

%S 0,8,94,1004,14864,334536,11546874,629381852,56094263348,

%T 8343512638896,2074276200162230,853966325494701152,

%U 578432462293854136504,646135466408339553958096,1200595044818176185884236342

%N Number of induced paths in the n X n grid graph.

%C Paths of length zero are not counted here.

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Induced_path">Induced path</a>

%e The a(2) = 8 induced paths are:

%e O O O . . . . O O O O . . O O O

%e . . O . O O . O O . O O O O . O

%Y Main diagonal of A360199.

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

%K nonn,more

%O 1,2

%A _Andrew Howroyd_, Jan 29 2023