login
Number of snake-like polyominoes in an n X n square that start at the NW corner and end at the SE corner and have the maximum length.
3

%I #29 Feb 28 2023 13:07:11

%S 1,2,6,20,2,64,44,512,28,4,64,520,480,6720,43232,14400

%N Number of snake-like polyominoes in an n X n square that start at the NW corner and end at the SE corner and have the maximum length.

%C The maximum length is given by A357234(n).

%C If the lower bounds of A357234(n) are tight, then a(14)-a(19) are 6720, 43232, 14400, 226560, 1646080, 403712.

%C For n > 1, a(n) is even since for every solution there is also the symmetrical solution reflected in the main diagonal.

%H Yi Yang, <a href="https://bbs.emath.ac.cn/thread-18542-4-1.html">The longest road in a square grid</a> (see 2nd post with a C++ program that generates a(2)-a(19)).

%e For n = 5, there are 2 such snakes shown as follows:

%e X . X X X X X X X X

%e X . X . X . . . . X

%e X . X . X X X X X X

%e X . X . X X . . . .

%e X X X . X X X X X X

%Y Cf. A331986, A357234.

%K nonn,walk,hard,more

%O 1,2

%A _Yi Yang_, Oct 01 2022

%E a(14)-a(16) from _Andrew Howroyd_, Feb 28 2023