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-8 of 8 results.

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

Original entry on oeis.org

1, 2, 2, 3, 5, 3, 4, 9, 9, 4, 5, 14, 24, 14, 5, 6, 20, 58, 58, 20, 6, 7, 27, 125, 229, 125, 27, 7, 8, 35, 251, 749, 749, 251, 35, 8, 9, 44, 490, 2180, 3436, 2180, 490, 44, 9, 10, 54, 948, 6188, 13350, 13350, 6188, 948, 54, 10, 11, 65, 1823, 17912, 50203, 65772, 50203, 17912, 1823, 65, 11
Offset: 2

Views

Author

Andrew Howroyd, Jan 29 2023

Keywords

Comments

Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4).

Examples

			Array begins:
========================================================
m\n| 2  3   4     5      6       7        8        9 ...
---+----------------------------------------------------
2  | 1  2   3     4      5       6        7        8 ...
3  | 2  5   9    14     20      27       35       44 ...
4  | 3  9  24    58    125     251      490      948 ...
5  | 4 14  58   229    749    2180     6188    17912 ...
6  | 5 20 125   749   3436   13350    50203   196918 ...
7  | 6 27 251  2180  13350   65772   308212  1535427 ...
8  | 7 35 490  6188  50203  308212  1743247 10614143 ...
9  | 8 44 948 17912 196918 1535427 10614143 78586742 ...
   ...

Links

Crossrefs

Main diagonal is A297664.
Rows 2..5 are A000027(n-1), A000096(n-1), A360197, A360198.
Cf. A231829 (undirected cycles), A287151 (connected induced subgraphs), A360199 (induced paths), A360202 (induced trees), A360913 (maximum induced cycles).

Formula

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

A357357 Length of the longest induced cycle in the n X n grid graph.

Original entry on oeis.org

0, 4, 8, 12, 16, 20, 32, 40, 50, 62, 76, 90, 104, 120, 140, 160, 180
Offset: 1

Views

Author

Pontus von Brömssen, Sep 25 2022

Keywords

Examples

			For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
Longest induced cycles for 6 <= n <= 8:
  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   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 . 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

Main diagonal of A360915.
Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).

Formula

a(n) <= A331968(n)+1.
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

Extensions

a(9)-a(12) from Elijah Beregovsky, Nov 24 2022
a(13) from Elijah Beregovsky, Nov 25 2022
a(14)-a(17) from Andrew Howroyd, Feb 26 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.

A360203 Number of (non-null) induced trees in the n X n grid graph.

Original entry on oeis.org

1, 12, 138, 3568, 277606, 66136452, 48136454388, 106601739449932, 716581962133166734, 14594259085593605592840, 899530518959027898354960664, 167638624754374503965030664785872, 94397539071875018677962029008899452442, 160524233982090828046095750880433748533447560
Offset: 1

Views

Author

Andrew Howroyd, Feb 22 2023

Keywords

Links

Crossrefs

Main diagonal of A360202.
Cf. A059525, A080691, A297664, A360200.

A360914 Number of maximum induced cycles in the n X n grid graph.

Original entry on oeis.org

0, 1, 1, 7, 90, 1398, 23, 2100, 6840, 2912, 416, 1344, 102198, 1643968, 42592, 48128, 1120128
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

A maximum induced cycle is an induced cycle of longest length.

Examples

			The a(3) = 1 unique cycle of longest length is:
   O O O
   O   O
   O O O
.
The a(4) = 7 maximum induced cycles have length 12 and are the following subgraphs with their rotations and reflections.
   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

Links

  • Eric Weisstein's World of Mathematics, Grid Graph.

Crossrefs

Main diagonal of A360913.
Cf. A297664, A357357 (lengths).

A361171 Number of chordless cycles in the n X n king graph.

Original entry on oeis.org

0, 0, 1, 13, 197, 4729, 156806, 7035482, 505265569, 82612843683, 33651820752580, 23922790371389972, 25614853328191562332, 43322613720440154974138, 128405885225433787867253690, 738840753928503040569961869076, 8481241718402438554921627740308746, 179685856472407342498054958799766397100
Offset: 1

Views

Author

Eric W. Weisstein, Mar 03 2023

Keywords

Comments

Using the convention that chordless cycles have length >= 4.

Links

Crossrefs

Cf. A140519, A234622, A297664, A357501.

Extensions

a(7)-a(18) from Andrew Howroyd, Mar 03 2023

A368657 Number of cycles in an n X n grid where the cycle cannot touch itself orthogonally or diagonally and must contain at least one inside point.

Original entry on oeis.org

0, 0, 1, 13, 167, 2685, 50391, 1188935, 41749885, 2645126227, 341643017303, 82472721488013, 31312529515504513, 17381378412860375479, 14419291783372365769995, 18997663191047558313462721
Offset: 1

Views

Author

Niklas Gustavsson, Jan 02 2024

Keywords

Comments

For n > 1, n < 5, this shares the sequence with n-1 in A140517. Cycles are not reduced by symmetry (rotation, translation or mirroring). The grid can only have one cycle.

Examples

			For n = 4, there are 13 valid cycles:
.
  1      2      3      4
  ###.   .###   ....   ....
  #.#.   .#.#   .###   ###.
  ###.   .###   .#.#   #.#.
  ....   ....   .###   ###.
.
  5      6      7     8
  ####   ....   ###.  .###
  #..#   ####   #.#.  .#.#
  ####   #..#   #.#.  .#.#
  ....   ####   ###.  .###
.
  9      10     11    12
  .###   ###.   ####  ####
  ##.#   #.##   #..#  #..#
  #..#   #..#   #.##  ##.#
  ####   ####   ###.  .###
.
  13
  ####
  #..#
  #..#
  ####

Links

Crossrefs

Cf. A140517, A297664.

A378400 Number of subsets of {1,2,3,...,n}^2 with the property that every point has exactly two other closest points.

Original entry on oeis.org

1, 1, 2, 8, 52, 676, 14463
Offset: 0

Views

Author

Erich Friedman, Nov 24 2024

Keywords

Examples

			For n=3, the a(3)=8 subsets are
  ...  oo.  .oo  ...  ...  ooo  .o.  o.o
  ...  oo.  .oo  oo.  .oo  o.o  o.o  ...
  ...  ...  ...  oo.  .oo  ooo  .o.  o.o
For n=4, the a(4)=52 subsets include
  .o..  .o..  oooo  oo.o  ..oo  ooo.
  o.o.  ...o  o..o  oo..  o.oo  o.o.
  .o..  o...  oo.o  ..oo  ....  o.o.
  ...o  ..o.  .ooo  ..oo  o.o.  ooo.

Crossrefs

Cf. A297664.

Programs

  • Mathematica
    d[p1_,p2_]:=(p1-p2).(p1-p2)
dists[L_,pt_]:=Sort[Map[d[pt,#]&,Complement[L,{pt}]]]
check[L_,pt_]:=(L =={})||((Length[L]>= 3)&&(dists[L,pt][[1]]==dists[L,pt][[2]])&&(dists[L,pt][[2]]< dists[L,pt][[3]]))
check[L_]:=Apply[And,Map[check[L, #]&,L]]
Table[Length[Select[Tuples[Tuples[{0,1},n],n],check[Position[#, 1]]&]],{n,0,5}]

Extensions

a(6) from Michael S. Branicky, Jan 01 2025
Showing 1-8 of 8 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.