cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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

Original entry on oeis.org

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182
Offset: 1

Views

Author

Alain Goupil, Feb 02 2020

Keywords

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.

Examples

			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

Links

Crossrefs

Main diagonal of A360917.
Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

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

Extensions

a(15) from Andrew Howroyd, Feb 04 2020
a(16)-a(17) from Yi Yang, Oct 03 2022

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Original entry on oeis.org

1, 4, 8, 84, 56, 136, 52, 216, 16, 1504, 2352, 1152, 1344, 123216, 82432, 11008, 308992
Offset: 1

Views

Author

Alain Goupil, Feb 03 2020

Keywords

Comments

The maximum possible number of unit squares is given by A331968(n).
Equivalently, a(n) is the number of maximum length paths without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
For n > 1, a(n) is a multiple of 4 since a solution can have at most one symmetry considering rotations and reflections. - Andrew Howroyd, Feb 04 2020

Examples

			For n = 4 the number of snake-like polyominoes with 11 cells is 84.

Links

  • Eric Weisstein's World of Mathematics, Grid Graph

Crossrefs

Main diagonal of A360916.
Cf. A331968, A059525 (connected induced subgraphs), A099155.
Cf. A332920 (non-isomorphic snakes), A332921 (symmetric snakes).

Extensions

a(15) from Andrew Howroyd, Feb 04 2020
a(16)-a(17) from Yi Yang, Oct 03 2022

A332920 Number of non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.

Original entry on oeis.org

1, 1, 2, 12, 8, 17, 8, 27, 3, 188
Offset: 1

Views

Author

Hugo Pfoertner, Mar 05 2020

Keywords

Comments

Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.

Examples

			a(4) = 12 (L = A331968(4) = 11):
  A332921(4) = 3 symmetric snakes
  . X O .     . X O O     . X O O     X . X O     X . X .     X . X O
  X . O O     X . . O     X . . O     O . . O     O . O O     O . . O
  O O . O     O . . O     O . O O     O . . O     O . . O     O . O O
  . O O O     O O O O     O O O .     O O O O     O O O O     O O O .
.
  X . X O     X . X .     X . X O     . X O .     . O O O     . O O O
  O . . O     O . O O     O O . O     X . O O     . X . O     . X . O
  O O . O     O O . O     . O . O     O . . O     X . . O     X . O O
  . O O O     . O O O     . O O O     O O O O     O O O O     O O O .
.
a(5) = 8 (L = 17)
  A332921(5) = 2 symmetric snakes
  O O O O X       O O O O O       O O O O O       X . O O X
  O . . . .       O . . . O       O . . . O       O . O . .
  O O O O O       O O . O O       O O X . O       O . O O O
  . . . . O       . O . O .       . . . . O       O . . . O
  X O O O O       X O . O X       X O O O O       O O O O O
.
  O O O O .       O O O O O       X . O O X       O O O O .
  O . . O O       O . . . O       O . O . .       O . . O O
  O O X . O       O O X . O       O . O O O       O O X . O
  . . . . O       . . . O O       O O . . O       . . . O O
  X O O O O       X O O O .       . O O O O       X O O O .

Crossrefs

Cf. A331968 (maximum length), A331986 (counts including isomorphisms), A332921 (subset of symmetric snakes).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.