A360196 -id:A360196 - cp's OEIS frontend

A297664 Number of chordless cycles in the n X n grid graph.

0, 1, 5, 24, 229, 3436, 65772, 1743247, 78586742, 7234839185, 1330059590925, 421587920205546, 212201572752086670, 170288846375423693683, 227570453486998336648738, 527014715702923506908210573, 2140337449056844246626590305042, 15055309813180236733267168372538873

Offset: 1

Eric W. Weisstein, Jan 02 2018

nonn

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360196.

Cf. A003763, A140517, A360200, A360914.

a(7)-a(18) from Andrew Howroyd, Jan 08 2018

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

Original entry on oeis.org

0, 1, 1, 3, 8, 3, 6, 25, 25, 6, 10, 58, 94, 58, 10, 15, 117, 270, 270, 117, 15, 21, 218, 681, 1004, 681, 218, 21, 28, 387, 1597, 3330, 3330, 1597, 387, 28, 36, 666, 3592, 10224, 14864, 10224, 3592, 666, 36, 45, 1123, 7880, 29924, 61165, 61165, 29924, 7880, 1123, 45

Offset: 1

Andrew Howroyd, Jan 29 2023

Paths of length zero are not counted here.

			Array begins:
============================================================
m\n|  1   2    3     4      5       6        7         8 ...
---+--------------------------------------------------------
1  |  0   1    3     6     10      15       21        28 ...
2  |  1   8   25    58    117     218      387       666 ...
3  |  3  25   94   270    681    1597     3592      7880 ...
4  |  6  58  270  1004   3330   10224    29924     85036 ...
5  | 10 117  681  3330  14864   61165   238897    907148 ...
6  | 15 218 1597 10224  61165  334536  1723535   8647932 ...
7  | 21 387 3592 29924 238897 1723535 11546874  75134416 ...
8  | 28 666 7880 85036 907148 8647932 75134416 629381852 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Induced path.

Main diagonal is A360200.
Rows 1..2 are A000217(n-1), A360201.
Cf. A287151 (induced connected subgraphs), A288518 (undirected paths), A360196 (induced cycles), A360202 (induced trees), A360916 (maximum induced paths).

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

Andrew Howroyd, Feb 22 2023

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

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Induced Subgraph.

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

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

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

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 4, 5, 5, 4, 10, 14, 21, 14, 10, 20, 30, 58, 58, 30, 20, 35, 55, 125, 236, 125, 55, 35, 56, 91, 231, 720, 720, 231, 91, 56, 84, 140, 385, 1754, 4040, 1754, 385, 140, 84, 120, 204, 596, 3654, 15550, 15550, 3654, 596, 204, 120

Offset: 1

Andrew Howroyd, Feb 24 2023

Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4). See A360849 for the version that excludes triangles.

			Array begins:
==========================================================
m\n|  1   2   3    4      5       6        7         8 ...
---+------------------------------------------------------
1  |  0   0   1    4     10      20       35        56 ...
2  |  0   1   5   14     30      55       91       140 ...
3  |  1   5  21   58    125     231      385       596 ...
4  |  4  14  58  236    720    1754     3654      6808 ...
5  | 10  30 125  720   4040   15550    45395    109840 ...
6  | 20  55 231 1754  15550  114105   526505   1776676 ...
7  | 35  91 385 3654  45395  526505  4662721  24865260 ...
8  | 56 140 596 6808 109840 1776676 24865260 256485936 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Rook Graph.
Wikipedia, Cycle (graph theory).

Main diagonal is A360854.
Rows 1..2 are A000292(n-2), A000330(n-1).
Cf. A360196, A360849, A360851 (induced paths), A360855 (triangles).

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

T(m,n) = A360849(m,n) + A360855(m,n).

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

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

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 1, 1, 4, 5, 1, 7, 1, 5, 6, 1, 17, 17, 1, 6, 7, 1, 31, 90, 31, 1, 7, 8, 1, 8, 284, 284, 8, 1, 8, 9, 1, 40, 9, 1398, 9, 40, 1, 9, 10, 1, 120, 163, 10, 10, 163, 120, 1, 10, 11, 1, 8, 1329, 382, 23, 382, 1329, 8, 1, 11, 12, 1, 64, 128, 6098, 190, 190, 6098, 128, 64, 1, 12

Offset: 2

Andrew Howroyd, Feb 26 2023

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

			Array begins:
=========================================
m\n| 2  3   4    5    6   7    8    9 ...
---+-------------------------------------
2  | 1  2   3    4    5   6    7    8 ...
3  | 2  1   1    1    1   1    1    1 ...
4  | 3  1   7   17   31   8   40  120 ...
5  | 4  1  17   90  284   9  163 1329 ...
6  | 5  1  31  284 1398  10  382 6098 ...
7  | 6  1   8    9   10  23  190  388 ...
8  | 7  1  40  163  382 190 2100   80 ...
9  | 8  1 120 1329 6098 388   80 6840 ...
  ...

Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal is A360914.

Cf. A360196 (induced cycles), A360915 (lengths), A360916, A360918.

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

Andrew Howroyd, Feb 26 2023

All terms are even since the grid graph is bipartite.

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

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal is A357357.

Cf. A360196, A360913, A360917, A360920.

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

A360197 Number of induced cycles in the 4 X n grid graph.

Original entry on oeis.org

0, 3, 9, 24, 58, 125, 251, 490, 948, 1823, 3485, 6636, 12614, 23961, 45495, 86350, 163856, 310899, 589873, 1119144, 2123266, 4028261, 7642379, 14499018, 27507300, 52186343, 99006909, 187833924, 356354718, 676068905, 1282624071, 2433368030, 4616535768

Offset: 1

Andrew Howroyd, Jan 29 2023

			The a(3) = 9 chordless cycles consist of six 1 X 1 squares (covering 4 vertices), four 2 X 2 squares and one 2 X 3 rectangle.
The a(4) = 24 solutions for the 4 X 4 grid include:
    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

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,5,-2,-1,1).

Row 4 of A360196.

LinearRecurrence[{4, -6, 5, -2, -1, 1}, {0, 3, 9, 24, 58, 125}, 50] (* Paolo Xausa, Jun 24 2024 *)

seq(n) = Vec(x*(3 - 3*x + 6*x^2 + x^3 - 2*x^4)/((1 - x)^2*(1 - 2*x + x^2 - x^3 - x^4)) + O(x^n), -n)

a(n) = 4*a(n-1) - 6*a(n-2) + 5*a(n-3) - 2*a(n-4) - a(n-5) + a(n-6) for n > 6.

G.f.: x^2*(3 - 3*x + 6*x^2 + x^3 - 2*x^4)/((1 - x)^2*(1 - 2*x + x^2 - x^3 - x^4)).

A360198 Number of induced cycles in the 5 X n grid graph.

Original entry on oeis.org

0, 4, 14, 58, 229, 749, 2180, 6188, 17912, 52620, 154383, 450195, 1309452, 3811888, 11110432, 32392550, 94412963, 275116777, 801676752, 2336222946, 6808405238, 19841419978, 57821971765, 168504312515, 491055599116, 1431039769316, 4170353383134, 12153282490316, 35417189532323

Offset: 1

Andrew Howroyd, Jan 29 2023

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (6,-14,17,-3,-17,16,-2,9,-27,5,19,-3,-2,-5,2).

Row 5 of A360196.

G.f.: x^2*(4 - 10*x + 30*x^2 + 9*x^3 - 39*x^4 + 16*x^5 + 49*x^6 + 28*x^7 - 76*x^8 - 58*x^9 + 7*x^10 + 13*x^11 + 9*x^12 - 4*x^13)/((1 - x)^2*(1 - 4*x + 5*x^2 - 3*x^3 - 8*x^4 + 4*x^5 - 2*x^7 - 13*x^8 + 3*x^9 + 14*x^10 + 6*x^11 + x^12 - 2*x^13)).

Missing a(1)=0 inserted by Andrew Howroyd, Feb 23 2023

cp's OEIS Frontend

A297664 Number of chordless cycles in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A360197 Number of induced cycles in the 4 X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360198 Number of induced cycles in the 5 X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions