|
|
A331968
|
|
Maximum number of unit squares of a snake-like polyomino in an n X n square box.
|
|
11
|
|
|
1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.
|
|
LINKS
|
|
|
FORMULA
|
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
|
|
EXAMPLE
|
For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
X X X X X X X X X X
X X X X X
X X X X
X X X
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(16)-a(17) from Yi Yang, Oct 03 2022
|
|
STATUS
|
approved
|
|
|
|