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-6 of 6 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

A360916 Array read by antidiagonals: T(m,n) is the number of maximum induced paths in the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 2, 2, 1, 1, 6, 8, 6, 1, 1, 2, 14, 14, 2, 1, 1, 8, 18, 84, 18, 8, 1, 1, 2, 2, 26, 26, 2, 2, 1, 1, 10, 4, 32, 56, 32, 4, 10, 1, 1, 2, 6, 16, 4, 4, 16, 6, 2, 1, 1, 12, 8, 152, 24, 136, 24, 152, 8, 12, 1, 1, 2, 10, 48, 32, 10, 10, 32, 48, 10, 2, 1
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

A maximum induced path is an induced path of longest length.
T(m,n) is the number of snake-like polyominoes with the maximum possible number of unit squares in an m X n rectangle.

Examples

			Array begins:
========================================
m\n| 1  2  3   4   5   6   7   8   9 ...
---+------------------------------------
1  | 1  1  1   1   1   1   1   1   1 ...
2  | 1  4  2   6   2   8   2  10   2 ...
3  | 1  2  8  14  18   2   4   6   8 ...
4  | 1  6 14  84  26  32  16 152  48 ...
5  | 1  2 18  26  56   4  24  32 108 ...
6  | 1  8  2  32   4 136  10 168  32 ...
7  | 1  2  4  16  24  10  52   4   8 ...
8  | 1 10  6 152  32 168   4 216   8 ...
9  | 1  2  8  48 108  32   8   8  16 ...
  ...

Links

Crossrefs

Main diagonal is A331986.
Cf. A360199, A360913, A360917 (lengths), A360918.

Formula

T(m,n) = T(n,m).

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).

A332921 Number of symmetric 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, 3, 2, 0, 3, 0, 2, 0
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(1) = 1 (L = A331968(1) = 1):
  X
.
a(2) = 1 (L = 3):
  X O
  . X
.
a(3) = 2 (L = 7):
  X O O    . X O
  . . O    X . O
  X O O    O O O
.
a(4) = 3 (L = 11)
  . X O .     . X O O     . X O 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 .
.
a(5) = 2 (L = 17)
  O O O O X      O O O O O
  O . . . .      O . . . O
  O O O O O      O O . O O
  . . . . O      . O . O .
  X O O O O      X O . O X
.
a(7) = 3 (L = 33)
  O O O . O O O     O 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 O . O O .
  . O O . O O .     O O . O . O O     X . O . O . x
  X . O . O . X     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
.
a(9) = 2 (L = 53)
  . O X . O O O O O    O 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 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 O .    O O O O O . X O O
.
Example for a(9) corrected by _Luke Murphy_, Oct 14 2024

Crossrefs

Cf. A331968, A331986, A332920.

A357516 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.

Original entry on oeis.org

1, 2, 6, 20, 2, 64, 44, 512, 28, 4, 64, 520, 480, 6720, 43232, 14400
Offset: 1

Views

Author

Yi Yang, Oct 01 2022

Keywords

Comments

The maximum length is given by A357234(n).
If the lower bounds of A357234(n) are tight, then a(14)-a(19) are 6720, 43232, 14400, 226560, 1646080, 403712.
For n > 1, a(n) is even since for every solution there is also the symmetrical solution reflected in the main diagonal.

Examples

			For n = 5, there are 2 such snakes shown as follows:
  X . X X X         X X X X X
  X . X . X         . . . . X
  X . X . X         X X X X X
  X . X . X         X . . . .
  X X X . X         X X X X X

Links

Crossrefs

Cf. A331986, A357234.

Extensions

a(14)-a(16) from Andrew Howroyd, Feb 28 2023

A360200 Number of induced paths in the n X n grid graph.

Original entry on oeis.org

0, 8, 94, 1004, 14864, 334536, 11546874, 629381852, 56094263348, 8343512638896, 2074276200162230, 853966325494701152, 578432462293854136504, 646135466408339553958096, 1200595044818176185884236342
Offset: 1

Views

Author

Andrew Howroyd, Jan 29 2023

Keywords

Comments

Paths of length zero are not counted here.
Equivalently, a(n) is the number of snake-like polyominoes in an n X n square. Rotations, reflections and translations are counted separately.

Examples

			The a(2) = 8 induced paths are:
  O O   O .   . .   . O   O O   O .   . O   O O
  . .   O .   O O   . O   O .   O O   O O   . O

Links

Crossrefs

Main diagonal of A360199.
Cf. A059525, A297664 (induced cycles), A331968, A331986 (of maximum length), A357516.
Showing 1-6 of 6 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.