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

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

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 6, 8, 9, 9, 8, 6, 7, 9, 12, 12, 12, 9, 7, 8, 11, 14, 15, 15, 14, 11, 8, 9, 12, 16, 18, 19, 18, 16, 12, 9, 10, 14, 18, 21, 22, 22, 21, 18, 14, 10, 11, 15, 21, 24, 26, 26, 26, 24, 21, 15, 11, 12, 17, 23, 27, 30, 31, 31, 30, 27, 23, 17, 12
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Examples

			Array begins:
===============================================
  m\n|  1  2  3  4  5  6  7  8  9 10 11  12 ...
-----+-----------------------------------------
   1 |  1  2  3  4  5  6  7  8  9 10 11  12 ...
   2 |  2  3  5  6  8  9 11 12 14 15 17  18 ...
   3 |  3  5  7  9 12 14 16 18 21 23 25  27 ...
   4 |  4  6  9 12 15 18 21 24 27 30 33  36 ...
   5 |  5  8 12 15 19 22 26 30 34 37 41  44 ...
   6 |  6  9 14 18 22 26 31 35 39 44 48  52 ...
   7 |  7 11 16 21 26 31 36 41 46 51 56  61 ...
   8 |  8 12 18 24 30 35 41 46 52 58 63  69 ...
   9 |  9 14 21 27 34 39 46 52 59 65 71  78 ...
  10 | 10 15 23 30 37 44 51 58 65 72 79  86 ...
  11 | 11 17 25 33 41 48 56 63 71 79 87  94 ...
  12 | 12 18 27 36 44 52 61 69 78 86 94 102 ...
  ...

Links

Crossrefs

Main diagonal is A360921.
Cf. A360915, A360917, A360918 (maximum induced trees).

Formula

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

A360915 Array read by antidiagonals: T(m,n) is the length of the longest induced cycle in the grid graph P_m X P_n.

Original entry on oeis.org

4, 4, 4, 4, 8, 4, 4, 10, 10, 4, 4, 12, 12, 12, 4, 4, 14, 14, 14, 14, 4, 4, 16, 16, 16, 16, 16, 4, 4, 18, 20, 18, 18, 20, 18, 4, 4, 20, 22, 24, 20, 24, 22, 20, 4, 4, 22, 24, 26, 28, 28, 26, 24, 22, 4, 4, 24, 28, 28, 30, 32, 30, 28, 28, 24, 4, 4, 26, 30, 32, 32, 36, 36, 32, 32, 30, 26, 4
Offset: 2

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

All terms are even since the grid graph is bipartite.

Examples

			Array begins:
==========================================
  m\n| 2  3  4  5  6  7  8  9 10 11 12 ...
-----+------------------------------------
   2 | 4  4  4  4  4  4  4  4  4  4  4 ...
   3 | 4  8 10 12 14 16 18 20 22 24 26 ...
   4 | 4 10 12 14 16 20 22 24 28 30 32 ...
   5 | 4 12 14 16 18 24 26 28 32 36 38 ...
   6 | 4 14 16 18 20 28 30 32 36 42 44 ...
   7 | 4 16 20 24 28 32 36 40 44 48 52 ...
   8 | 4 18 22 26 30 36 40 46 50 56 60 ...
   9 | 4 20 24 28 32 40 46 50 56 62 68 ...
  10 | 4 22 28 32 36 44 50 56 62 70 74 ...
  11 | 4 24 30 36 42 48 56 62 70 76 82 ...
  12 | 4 26 32 38 44 52 60 68 74 82 90 ...
  ...

Links

Crossrefs

Main diagonal is A357357.
Cf. A360196, A360913, A360917, A360920.

Formula

T(m,n) = T(n,m).
T(m,n) = 2*m*n/3 + O(m+n) (Beluhov 2023, Proposition 3). - Pontus von Brömssen, May 08 2023
Showing 1-4 of 4 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.