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

A360202 Array read by antidiagonals: T(m,n) is the number of (non-null) induced trees in the grid graph P_m X P_n.

Original entry on oeis.org

1, 3, 3, 6, 12, 6, 10, 33, 33, 10, 15, 78, 138, 78, 15, 21, 171, 533, 533, 171, 21, 28, 360, 2003, 3568, 2003, 360, 28, 36, 741, 7453, 23686, 23686, 7453, 741, 36, 45, 1506, 27643, 156614, 277606, 156614, 27643, 1506, 45, 55, 3039, 102432, 1034875, 3234373, 3234373, 1034875, 102432, 3039, 55
Offset: 1

Views

Author

Andrew Howroyd, Feb 22 2023

Keywords

Examples

			Array begins:
=============================================================
m\n|  1   2     3       4        5          6           7 ...
---+---------------------------------------------------------
1  |  1   3     6      10       15         21          28 ...
2  |  3  12    33      78      171        360         741 ...
3  |  6  33   138     533     2003       7453       27643 ...
4  | 10  78   533    3568    23686     156614     1034875 ...
5  | 15 171  2003   23686   277606    3234373    37643572 ...
6  | 21 360  7453  156614  3234373   66136452  1349087217 ...
7  | 28 741 27643 1034875 37643572 1349087217 48136454388 ...
     ...

Links

Crossrefs

Main diagonal is A360203.
Rows 1..2 are A000217, 3*A125128.
Cf. A287151 (connected induced subgraphs), A116469 (spanning trees), A360196 (induced cycles), A360199 (induced paths), A360918 (maximum induced trees).

Formula

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

A360851 Array read by antidiagonals: T(m,n) is the number of induced paths in the rook graph K_m X K_n.

Original entry on oeis.org

0, 1, 1, 3, 8, 3, 6, 27, 27, 6, 10, 64, 126, 64, 10, 15, 125, 426, 426, 125, 15, 21, 216, 1125, 2208, 1125, 216, 21, 28, 343, 2493, 8830, 8830, 2493, 343, 28, 36, 512, 4872, 27456, 55700, 27456, 4872, 512, 36, 45, 729, 8676, 70434, 265635, 265635, 70434, 8676, 729, 45
Offset: 1

Views

Author

Andrew Howroyd, Feb 24 2023

Keywords

Comments

Paths of length zero are not counted here.

Examples

			Array begins:
===================================================
m\n|  1   2    3     4      5        6        7 ...
---+-----------------------------------------------
1  |  0   1    3     6     10       15       21 ...
2  |  1   8   27    64    125      216      343 ...
3  |  3  27  126   426   1125     2493     4872 ...
4  |  6  64  426  2208   8830    27456    70434 ...
5  | 10 125 1125  8830  55700   265635   961975 ...
6  | 15 216 2493 27456 265635  2006280 11158161 ...
7  | 21 343 4872 70434 961975 11158161 98309778 ...
  ...

Links

Crossrefs

Main diagonal is A360852.
Rows 1..2 are A000217(n-1), A000578.
Cf. A003991, A360199, A360850.

Programs

  • PARI
    T(m,n) = sum(j=1, min(m,n), j!^2*binomial(m,j)*binomial(n,j)*(1 + (m+n)/2 - j)) - m*n

Formula

T(m,n) = A360850(m,n) - A003991(m,n).
T(m,n) = -m*n + Sum_{j=1..min(m,n)} j!^2*binomial(m,j)*binomial(n,j)*(1 + (m+n)/2 - j).
T(m,n) = T(n,m).

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

A360917 Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path 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, 11, 11, 11, 9, 7, 8, 11, 14, 14, 14, 14, 11, 8, 9, 12, 16, 17, 17, 17, 16, 12, 9, 10, 14, 18, 20, 21, 21, 20, 18, 14, 10, 11, 15, 20, 22, 24, 24, 24, 22, 20, 15, 11, 12, 17, 22, 25, 27, 29, 29, 27, 25, 22, 17, 12
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.

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 11 14 16 18 20 22 24 26 ...
   4 |  4  6  9 11 14 17 20 22 25 28 30 33 ...
   5 |  5  8 11 14 17 21 24 27 30 34 37 40 ...
   6 |  6  9 14 17 21 24 29 32 36 40 44 47 ...
   7 |  7 11 16 20 24 29 33 38 42 46 50 55 ...
   8 |  8 12 18 22 27 32 38 42 48 52 57 62 ...
   9 |  9 14 20 25 30 36 42 48 53 58 64 70 ...
  10 | 10 15 22 28 34 40 46 52 58 64 71 77 ...
  11 | 11 17 24 30 37 44 50 57 64 71 77 86 ...
  12 | 12 18 26 33 40 47 55 62 70 77 86 92 ...
  ...

Links

Crossrefs

Main diagonal is A331968.
Cf. A360199, A360915, A360916 (maximum induced paths), 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

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.

A360201 Number of induced paths in the n-ladder graph P_2 X P_n.

Original entry on oeis.org

1, 8, 25, 58, 117, 218, 387, 666, 1123, 1868, 3079, 5044, 8229, 13388, 21741, 35262, 57145, 92558, 149863, 242590, 392631, 635408, 1028235, 1663848, 2692297, 4356368, 7048897, 11405506, 18454653, 29860418, 48315339, 78176034, 126491659, 204667988
Offset: 1

Views

Author

Andrew Howroyd, Jan 29 2023

Keywords

Links

Crossrefs

Row 2 of A360199.

Programs

  • Mathematica
    LinearRecurrence[{3,-2,-1,1},{1,8,25,58},40] (* Harvey P. Dale, Dec 28 2023 *)
  • PARI
    Vec((1 + 5*x + 3*x^2)/((1 - x)^2*(1 - x - x^2)) + O(x^40))

Formula

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n > 4.
G.f.: x*(1 + 5*x + 3*x^2)/((1 - x)^2*(1 - x - x^2)).
Showing 1-7 of 7 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.