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-10 of 15 results. Next

A059525 Number of nonzero n X n binary arrays with all 1's connected.

Original entry on oeis.org

0, 1, 13, 218, 11506, 2301877, 1732082741, 4872949974666, 51016818604894742, 1980555831431088025753, 284374318545830329487309785, 150730745416633777472365437495914, 294516896499779486414143877573183893666, 2119097214294718323017954923662829194285541981
Offset: 0

Views

Author

David Radcliffe, Jan 21 2001

Keywords

Comments

Old name was: "Number of n X n checkerboards in which the set of red squares is edge connected".
Also the number of connected induced (non-null) subgraphs of the n X n grid graph P_n x P_n. - Eric W. Weisstein, May 01 2017

Links

Crossrefs

Main diagonal of A287151.
Cf. A059021, A020873 (wheel), A059020 (ladder), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

Programs

Extensions

One more term from John W. Layman, Jan 25 2001
More terms from R. H. Hardin, Feb 28 2002
Clearer name from R. H. Hardin, Jul 06 2009
a(8)-a(9) from Giovanni Resta, May 03 2017
a(10)-a(13) from Andrew Howroyd, May 20 2017

A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

Original entry on oeis.org

0, 3, 13, 40, 108, 275, 681, 1664, 4040, 9779, 23637, 57096, 137876, 332899, 803729, 1940416, 4684624, 11309731, 27304157, 65918120, 159140476, 384199155, 927538873, 2239276992, 5406092952, 13051462995, 31509019045, 76069501192, 183648021540, 443365544387
Offset: 0

Views

Author

John W. Layman, Dec 14 2000

Keywords

Comments

In other words, the number of connected (non-null) induced subgraphs in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, May 02 2017
Also, the number of cycles in the grid graph P_3 X P_{n+1}. - Andrew Howroyd, Jun 12 2017

Links

Crossrefs

Row 2 of A287151 and row 2 of A231829.
See also A059021, A059524.
Cf. A000129. - Jaume Oliver Lafont, Sep 28 2009
Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.

Programs

  • Magma
    I:=[0, 3, 13, 40];[n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4):n in [1..30]]; // Marius A. Burtea, Aug 25 2019
  • Mathematica
    Join[{0},LinearRecurrence[{4, -4, 0, 1}, {3, 13, 40, 108}, 20]] (* Eric W. Weisstein, May 02 2017 *) (* adapted by Vincenzo Librandi, May 09 2017 *)
Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* Eric W. Weisstein, May 02 2017 *)

Formula

a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.
From Jaume Oliver Lafont, Nov 23 2008: (Start)
a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)
G.f.: x*(3+x)/((1-2*x-x^2)*(1-x)^2). - Jaume Oliver Lafont, Sep 28 2009
Empirical observations (from Superseeker):
(1) if b(n) = a(n) + n then {b(n)} is A048777;
(2) if b(n) = a(n+3) - 3*a(n+2) - 3*a(n+1) + a(n) then {b(n)} is A052542;
(3) if b(n) = a(n+2) - 2*a(n+1) + a(n) then {b(n)} is A001333.
4*a(n) = A002203(n+3) - 8*n - 14. - Eric W. Weisstein, May 02 2017
a(n) = 3*A048776(n-1) + A048776(n-2). - R. J. Mathar, May 12 2019
E.g.f.: (1/2)*exp(x)*(-7-4*x+7*cosh(sqrt(2)*x)+5*sqrt(2)*sinh(sqrt(2)*x)). - Stefano Spezia, Aug 25 2019

A292357 Array read by antidiagonals: T(m,n) is the number of fixed polyominoes that have a width of m and height of n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 15, 15, 1, 1, 39, 111, 39, 1, 1, 97, 649, 649, 97, 1, 1, 237, 3495, 7943, 3495, 237, 1, 1, 575, 18189, 86995, 86995, 18189, 575, 1, 1, 1391, 93231, 910667, 1890403, 910667, 93231, 1391, 1
Offset: 1

Views

Author

Andrew Howroyd, Oct 02 2017

Keywords

Comments

Equivalently, the number of m X n binary arrays with all 1's connected and at least one 1 on each edge.

Examples

			Array begins:
===============================================================
m\n| 1   2     3       4         5           6             7
---|-----------------------------------------------------------
1  | 1   1     1       1         1           1             1...
2  | 1   5    15      39        97         237           575...
3  | 1  15   111     649      3495       18189         93231...
4  | 1  39   649    7943     86995      910667       9339937...
5  | 1  97  3495   86995   1890403    38916067     782256643...
6  | 1 237 18189  910667  38916067  1562052227   61025668579...
7  | 1 575 93231 9339937 782256643 61025668579 4617328590967...
...
T(2,2) = 5 counts 4 3-ominoes of shape 2x2 and 1 4-omino of shape 2x2.
T(3,2) = 15 counts 8 4-ominoes of shape 3x2, 6 5-ominoes of shape 3x2, and 1 6-omino of shape 3x2.
T(4,2) = 39 counts 12 5-ominoes of shape 4x2, 18 6-ominoes of shape 4x2, 8 7-ominoes of shape 4x2, and 1 8-omino of shape 4x2.

Links

Crossrefs

Rows 2..4 are A034182, A034184, A034187.
Main diagonal is A268404.
Cf. A268371 (nonequivalent), A287151, A308359.

Programs

  • Mathematica
    A287151 = Import["https://oeis.org/A287151/b287151.txt", "Table"][[All, 2]];
imax = Length[A287151];
mmax = Sqrt[2 imax] // Ceiling;
Clear[V]; VV = Table[V[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten;
Do[Evaluate[VV[[i]]] = A287151[[i]], {i, 1, imax}];
V[0, ] = V[, 0] = 0;
T[m_, n_] := If[m == 1 || n == 1, 1, U[m, n] - 2 U[m, n-1] + U[m, n-2]];
U[m_, n_] := V[m, n] - 2 V[m-1, n] + V[m-2, n];
Table[T[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten // Take[#, imax]& (* Jean-François Alcover, Sep 22 2019 *)

Formula

T(m, n) = U(m, n) - 2*U(m, n-1) + U(m, n-2) where U(m, n) = V(m, n) - 2*V(m-1, n) + V(m-2, n) and V(m, n) = A287151(m, n).

A359574 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from top row to bottom row.

Original entry on oeis.org

1, 3, 1, 6, 7, 1, 10, 28, 17, 1, 15, 88, 144, 41, 1, 21, 245, 920, 730, 99, 1, 28, 639, 5191, 9362, 3692, 239, 1, 36, 1608, 27651, 104989, 94280, 18666, 577, 1, 45, 3968, 143342, 1111283, 2075271, 947760, 94384, 1393, 1, 55, 9689, 733512, 11457514, 42972329, 40792921, 9528128, 477264, 3363, 1
Offset: 1

Views

Author

Andrew Howroyd, Jan 06 2023

Keywords

Comments

The grid has m rows and n columns.

Examples

			Array begins:
================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   3     6      10        15          21            28 ...
2  | 1   7    28      88       245         639          1608 ...
3  | 1  17   144     920      5191       27651        143342 ...
4  | 1  41   730    9362    104989     1111283      11457514 ...
5  | 1  99  3692   94280   2075271    42972329     866126030 ...
6  | 1 239 18666  947760  40792921  1642690309   64270256276 ...
7  | 1 577 94384 9528128 801218515 62618577481 4741764527414 ...
  ...

Links

Crossrefs

Main diagonal is A163028.
Rows 1..10 are A000217, A163037, A163038, A163039, A163040, A163041, A163042, A163043, A163044, A163045.
Columns 1..10 are A000012, A001333(n+1), A163029, A163030, A163031, A163032, A163033, A163034, A163035, A163036.
Cf. A287151, A292357, A359573, A359576.

Formula

T(m,n) = A287151(m,n) - 2*A287151(m-1,n) + A287151(m-2,n) for m > 2.

A359573 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from upper left corner to lower right corner.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 8, 1, 1, 20, 45, 20, 1, 1, 49, 234, 234, 49, 1, 1, 119, 1193, 2423, 1193, 119, 1, 1, 288, 6049, 24455, 24455, 6049, 288, 1, 1, 696, 30616, 245972, 482443, 245972, 30616, 696, 1, 1, 1681, 154861, 2473317, 9469361, 9469361, 2473317, 154861, 1681, 1
Offset: 1

Views

Author

Andrew Howroyd, Jan 06 2023

Keywords

Examples

			Array begins:
================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   1     1       1         1           1             1 ...
2  | 1   3     8      20        49         119           288 ...
3  | 1   8    45     234      1193        6049         30616 ...
4  | 1  20   234    2423     24455      245972       2473317 ...
5  | 1  49  1193   24455    482443     9469361     185899132 ...
6  | 1 119  6049  245972   9469361   360923899   13742823032 ...
7  | 1 288 30616 2473317 185899132 13742823032 1012326365581 ...
  ...

Links

Crossrefs

Main diagonal is A163002.
Rows 1..10 are A000012, A048739(n-1), A163003, A163004, A163005, A163006, A163007, A163008, A163009, A163010.
Cf. A287151, A359574, A359575, A359576.

Formula

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

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

A378932 Array read by antidiagonals: T(m,n) is the number of minimal edge cuts in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 2, 6, 2, 3, 15, 15, 3, 4, 28, 53, 28, 4, 5, 45, 146, 146, 45, 5, 6, 66, 356, 627, 356, 66, 6, 7, 91, 809, 2471, 2471, 809, 91, 7, 8, 120, 1759, 9292, 16213, 9292, 1759, 120, 8, 9, 153, 3716, 33878, 103196, 103196, 33878, 3716, 153, 9, 10, 190, 7702, 120771, 642364, 1123743, 642364, 120771, 7702, 190, 10
Offset: 1

Views

Author

Andrew Howroyd, Dec 11 2024

Keywords

Comments

T(m,n) is the number of partitionings of an m X n checkerboard into two edgewise-connected sets.

Examples

			Table starts:
===================================================
m\n | 1  2    3     4      5        6         7 ...
----+----------------------------------------------
  1 | 0  1    2     3      4        5         6 ...
  2 | 1  6   15    28     45       66        91 ...
  3 | 2 15   53   146    356      809      1759 ...
  4 | 3 28  146   627   2471     9292     33878 ...
  5 | 4 45  356  2471  16213   103196    642364 ...
  6 | 5 66  809  9292 103196  1123743  12028981 ...
  7 | 6 91 1759 33878 642364 12028981 221984391 ...
  ...

Links

Crossrefs

Main diagonal is A068416.
Rows 1..4 are A001477(n-1), A000384, A378933, A378934.
Rows 3..8 multiplied by 2 are A166761, A166766, A166769, A166771, A166773, A166774.
Cf. A287151, A359990.

Formula

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

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

Views

Author

Andrew Howroyd, Jan 29 2023

Keywords

Comments

Paths of length zero are not counted here.

Examples

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

Links

Crossrefs

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

A291872 Array read by antidiagonals: T(m,n) = number of connected dominating sets in the grid graph P_m X P_n.

Original entry on oeis.org

1, 3, 3, 4, 9, 4, 4, 24, 24, 4, 4, 56, 129, 56, 4, 4, 136, 613, 613, 136, 4, 4, 328, 2997, 5617, 2997, 328, 4, 4, 792, 14713, 52955, 52955, 14713, 792, 4, 4, 1912, 72169, 502521, 964755, 502521, 72169, 1912, 4, 4, 4616, 353853, 4763717, 17625829, 17625829, 4763717, 353853, 4616, 4
Offset: 1

Views

Author

Andrew Howroyd, Sep 04 2017

Keywords

Examples

			Array begins:
===============================================================
m\n| 1   2     3       4         5           6             7
---|-----------------------------------------------------------
1  | 1   3     4       4         4           4             4...
2  | 3   9    24      56       136         328           792...
3  | 4  24   129     613      2997       14713         72169...
4  | 4  56   613    5617     52955      502521       4763717...
5  | 4 136  2997   52955    964755    17625829     321381919...
6  | 4 328 14713  502521  17625829   617429805   21550989109...
7  | 4 792 72169 4763717 321381919 21550989109 1436456861467...
...

Links

Crossrefs

Row 2 is A291706.
Main diagonal is A287690.
Cf. A218354 (dominating), A287151 (connected).
Cf. A291873 (king).

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).
Showing 1-10 of 15 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.