The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 Table of n, a(n) for n=1..17. Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023. Alain Goupil, Illustration of initial terms Eric Weisstein's World of Mathematics, Grid Graph FORMULA a(n) >= A047838(n+1). For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020 a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020 a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023 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 Main diagonal of A360917. Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359. Sequence in context: A211076 A180452 A294479 * A029715 A088803 A350146 Adjacent sequences: A331965 A331966 A331967 * A331969 A331970 A331971 KEYWORD nonn,hard,more AUTHOR Alain Goupil, Feb 02 2020 EXTENSIONS a(15) from Andrew Howroyd, Feb 04 2020 a(16)-a(17) from Yi Yang, Oct 03 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 22 08:47 EDT 2023. Contains 365519 sequences. (Running on oeis4.)