cp's OEIS Frontend

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

%I A331968 #87 Feb 16 2025 08:33:59
%S A331968 1,3,7,11,17,24,33,42,53,64,77,92,107,123,142,162,182
%N A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.
%C A331968 These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
%C A331968 The number of solutions is given by A331986(n).
%C A331968 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.
%C A331968 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.
%C A331968 a(16) >= 161.
%H A331968 Nikolai Beluhov, <a href="https://arxiv.org/abs/2301.01152">Snake paths in king and knight graphs</a>, arXiv:2301.01152 [math.CO], 2023.
%H A331968 Alain Goupil, <a href="/A331968/a331968_2.pdf">Illustration of initial terms</a>
%H A331968 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%F A331968 a(n) >= A047838(n+1).
%F A331968 For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - _Elijah Beregovsky_, May 11 2020
%F A331968 a(n) <= (2*n*(n+1)-1)/3. - _Elijah Beregovsky_, Nov 09 2020
%F A331968 a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - _Pontus von Brömssen_, Jan 30 2023
%e A331968 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.
%e A331968 Maximum-length snakes for n = 1 to 4 are shown below.
%e A331968    X    X X    X X X    X X X X
%e A331968         X      X   X    X     X
%e A331968                X   X    X     X
%e A331968                         X   X X
%Y A331968 Main diagonal of A360917.
%Y A331968 Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.
%K A331968 nonn,hard,more
%O A331968 1,2
%A A331968 _Alain Goupil_, Feb 02 2020
%E A331968 a(15) from _Andrew Howroyd_, Feb 04 2020
%E A331968 a(16)-a(17) from _Yi Yang_, Oct 03 2022