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

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

Original entry on oeis.org

0, 1, 1, 3, 11, 3, 7, 105, 105, 7, 15, 919, 3665, 919, 15, 31, 7713, 123215, 123215, 7713, 31, 63, 63351, 4051679, 16222021, 4051679, 63351, 63, 127, 514321, 131630449, 2108725953, 2108725953, 131630449, 514321, 127, 255, 4148839, 4248037953, 272179739279, 1089224690733, 272179739279, 4248037953, 4148839, 255
Offset: 1

Views

Author

Andrew Howroyd, Jan 28 2023

Keywords

Comments

The complement of an edge cut is a disconnected spanning subgraph (spanning meaning that the graph has the same vertex set although some vertices may be of degree zero).

Examples

			Table starts:
========================================================
m\n|  1     2         3            4               5
---+----------------------------------------------------
1  |  0     1         3            7              15 ...
2  |  1    11       105          919            7713 ...
3  |  3   105      3665       123215         4051679 ...
4  |  7   919    123215     16222021      2108725953 ...
5  | 15  7713   4051679   2108725953   1089224690733 ...
6  | 31 63351 131630449 272179739279 560238057496423 ...
   ...

Links

  • Eric Weisstein's World of Mathematics, Edge Cut
  • Eric Weisstein's World of Mathematics, Grid Graph

Crossrefs

Rows 1..3 are A000225(n-1), A359987, A359988.
Main diagonal is A359989.
Cf. A141387, A359993 (connected spanning subgraphs).

Formula

T(m,n) = 2^B(m,n) - A359993(m,n) where B(m,n) = 2*m*n - m - n = A141387(n+m-2, n-1) is the number of edges in the graph.
T(m,n) = T(n,m).

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Original entry on oeis.org

1, 5, 431, 555195, 10286937043, 2692324030864335, 9852929684161379901975, 501079193080617800221189943995, 352690403996687922642590703716802346343, 3426297680513758764075706102615040790667832304415, 458508006189588425325361635000918336126387961057365005349963
Offset: 1

Views

Author

Andrew Howroyd, Jan 28 2023

Keywords

Comments

For n > 1, a(n) is the number of connected edge covers in the n X n grid graph.

Examples

			The a(2) = 5 connected spanning subgraphs are the following subgraphs and their rotations and reflections.
   o---o   o---o
   |       |   |
   o---o   o---o

Links

Crossrefs

Main diagonal of A359993.
Cf. A007341, A053765, A080691, A286913, A359989.

Formula

a(n) = A053765(n) - A359989(n).

A359987 Number of edge cuts in the n-ladder graph P_2 X P_n.

Original entry on oeis.org

1, 11, 105, 919, 7713, 63351, 514321, 4148839, 33347041, 267489431, 2143168305, 17160184519, 137349160833, 1099102033911, 8794224638161, 70360221445159, 562911076526881, 4503422288363351, 36027988077717105, 288226686123491719, 2305826176955087553, 18446667292472959671
Offset: 1

Views

Author

Andrew Howroyd, Jan 28 2023

Keywords

Links

Crossrefs

Row 2 of A359990.
Cf. A013730, A107839, A356828 (vertex cuts), A359989.
Cf. A359621, A359622.

Programs

  • Mathematica
    LinearRecurrence[{13, -42, 16}, {1, 11, 105}, 25] (* Paolo Xausa, Jun 24 2024 *)
Table[2^(3 n - 2) + (((5 - Sqrt[17])/2)^n - ((5 + Sqrt[17])/2)^n)/Sqrt[17], {n, 20}] // Expand (* Eric W. Weisstein, Nov 03 2024 *)
CoefficientList[Series[-(1 - 2 x + 4 x^2)/((-1 + 8 x) (1 - 5 x + 2 x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Nov 03 2024 *)
  • PARI
    Vec((1 - 2*x + 4*x^2)/((1 - 8*x)*(1 - 5*x + 2*x^2)) + O(x^25))

Formula

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