A286912 -id:A286912 - cp's OEIS frontend

A286913 Number of edge covers in the grid graph P_n X P_n.

0, 7, 969, 2180738, 68534828391, 30833670159649637, 197887615273032627789510, 18126687290150589819559507400227, 23696879029605485832353513435527035363501, 442121584517675331278913696274915728729945474905362

Offset: 1

Andrew Howroyd, May 15 2017

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..12
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A286912.

Cf. A286911.

A286912 = Cases[Import["https://oeis.org/A286912/b286912.txt", "Table"], {, }][[All, 2]];
a[n_] := A286912[[2 n^2 - 2 n + 1]]; a[1] = 1;
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Sep 23 2019 *)

a(1) corrected by Andrew Howroyd, Jan 29 2023

A359993 Array read by antidiagonals: T(m,n) is the number of connected spanning subgraphs in the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 23, 23, 1, 1, 105, 431, 105, 1, 1, 479, 7857, 7857, 479, 1, 1, 2185, 142625, 555195, 142625, 2185, 1, 1, 9967, 2587279, 38757695, 38757695, 2587279, 9967, 1, 1, 45465, 46929343, 2698167665, 10286937043, 2698167665, 46929343, 45465, 1

Offset: 1

Andrew Howroyd, Jan 28 2023

Also T(m,n) except when m = n = 0 is the number of connected edge covers in the m X n grid graph.

			Table starts:
=================================================================
m\n| 1    2       3          4             5                6
---+-------------------------------------------------------------
1  | 1    1       1          1             1                1 ...
2  | 1    5      23        105           479             2185 ...
3  | 1   23     431       7857        142625          2587279 ...
4  | 1  105    7857     555195      38757695       2698167665 ...
5  | 1  479  142625   38757695   10286937043    2711895924889 ...
6  | 1 2185 2587279 2698167665 2711895924889 2692324030864335 ...
   ...

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

Rows 1..4 are A000012, A107839(n-1), A158453, A359991.
Main diagonal is A359992.
Cf. A116469 (spanning trees), A287151 (connected induced subgraphs), A286912 (edge covers), A359990 (edge cuts), A360194 (spanning forests).

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

A286911 Number of edge covers in the ladder graph P_2 x P_n.

Original entry on oeis.org

1, 7, 43, 277, 1777, 11407, 73219, 469981, 3016729, 19363879, 124293499, 797819173, 5121067777, 32871277183, 210995228083, 1354343064493, 8693301516841, 55800847838359, 358176305451691, 2299073773191541, 14757369859827601, 94725087867636847

Offset: 1

Andrew Howroyd, May 15 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Ladder Graph
Index entries for linear recurrences with constant coefficients, signature (6, 3, -2).

Row 2 of A286912.

Cf. A123304, A020866.

Table[-RootSum[2 - 3 # - 6 #^2 + #^3 &, -14 #^n - 5 #^(n + 1) + #^(n + 2) &]/30, {n, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
LinearRecurrence[{6, 3, -2}, {1, 7, 43}, 20] (* Eric W. Weisstein, Aug 09 2017 *)
CoefficientList[Series[(1 + x - 2 x^2)/(1 - 6 x - 3 x^2 + 2 x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 09 2017 *)

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

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

A288025 Array read by antidiagonals: T(m,n) = number of minimal edge covers in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 6, 6, 1, 2, 17, 38, 17, 2, 2, 45, 190, 190, 45, 2, 3, 120, 1021, 1834, 1021, 120, 3, 4, 324, 5494, 19988, 19988, 5494, 324, 4, 5, 873, 29042, 208186, 419710, 208186, 29042, 873, 5, 7, 2349, 154772, 2177591, 8704085, 8704085, 2177591, 154772, 2349, 7

Offset: 1

Andrew Howroyd, Jun 04 2017

A minimal edge cover is an edge cover such that the removal of any edge in the cover destroys the covering property. Equivalently, these are the edge covers whose connected components are stars. A minimal edge cover is not the same as a minimum edge cover.

			Table starts:
================================================================
m\n| 1   2     3       4         5           6             7
---|------------------------------------------------------------
1  | 0   1     1       1         2           2             3 ...
2  | 1   2     6      17        45         120           324 ...
3  | 1   6    38     190      1021        5494         29042 ...
4  | 1  17   190    1834     19988      208186       2177591 ...
5  | 2  45  1021   19988    419710     8704085     179649371 ...
6  | 2 120  5494  208186   8704085   356269056   14484264119 ...
7  | 3 324 29042 2177591 179649371 14484264119 1163645044100 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Main diagonal is A288027.
Rows 1-3 are A182097, A288029, A288030.
Cf. A286912.

A284938 Triangle read by rows: coefficients of the edge cover polynomial for the n-path graph P_n.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 3, 4, 1, 0, 0, 0, 0, 1, 6, 5, 1, 0, 0, 0, 0, 0, 4, 10, 6, 1, 0, 0, 0, 0, 0, 1, 10, 15, 7, 1, 0, 0, 0, 0, 0, 0, 5, 20, 21, 8, 1, 0, 0, 0, 0, 0, 0, 1, 15, 35, 28, 9, 1, 0, 0, 0, 0, 0, 0, 0, 6, 35, 56, 36, 10, 1, 0, 0, 0, 0, 0, 0, 0, 1, 21, 70, 84, 45, 11, 1

Offset: 1

Eric W. Weisstein, Apr 06 2017

			0;
0,1;
0,0,1;
0,0,1,1;
0,0,0,2,1;
0,0,0,1,3,1;
0,0,0,0,3,4,1;
0,0,0,0,1,6,5,1;
0,0,0,0,0,4,10,6,1;
0,0,0,0,0,1,10,15,7,1;
0,0,0,0,0,0,5,20,21,8,1;
0,0,0,0,0,0,1,15,35,28,9,1;
0,0,0,0,0,0,0,6,35,56,36,10,1;
0,0,0,0,0,0,0,1,21,70,84,45,11,1;
...

Eric Weisstein's World of Mathematics, Edge Cover Polynomial
Eric Weisstein's World of Mathematics, Path Graph

Unsigned version of A057094.
Row sums are A000045(n-1).
Cf. A286912, A258993, A030528, A085478, A098925, A102426, A143858, etc.

Prepend[CoefficientList[Table[x^(n/2) Fibonacci[n - 1, Sqrt[x]], {n, 2, 14}], x], {0}] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)
Prepend[CoefficientList[LinearRecurrence[{x, x}, {0, x}, {2, 14}], x], {0}] // Flatten (* Eric W. Weisstein, Apr 07 2017 *)

a(n) = abs(A057094(n)).

A288026 Array read by antidiagonals: T(m,n) = number of maximal matchings in the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 5, 5, 2, 3, 11, 22, 11, 3, 4, 24, 75, 75, 24, 4, 5, 51, 264, 400, 264, 51, 5, 7, 109, 941, 2357, 2357, 941, 109, 7, 9, 234, 3286, 13407, 22228, 13407, 3286, 234, 9, 12, 503, 11623, 76667, 207423, 207423, 76667, 11623, 503, 12

Offset: 1

Andrew Howroyd, Jun 04 2017

			Table starts:
=====================================================
m\n| 1   2    3     4       5        6          7
---|-------------------------------------------------
1  | 1   1    2     2       3        4          5 ...
2  | 1   2    5    11      24       51        109 ...
3  | 2   5   22    75     264      941       3286 ...
4  | 2  11   75   400    2357    13407      76667 ...
5  | 3  24  264  2357   22228   207423    1922112 ...
6  | 4  51  941 13407  207423  3136370   47256485 ...
7  | 5 109 3286 76667 1922112 47256485 1158560776 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Main diagonal is A287595.
Rows 1-3 are A182097(n+2), A286945, A288028.
Cf. A210662, A099390, A286912, A288025.

A288031 Number of edge covers in the grid graph P_3 X P_n.

Original entry on oeis.org

1, 43, 969, 23663, 571099, 13807469, 333735575, 8066926825, 194989463233, 4713185791699, 113924706164937, 2753729539353359, 66561737202707371, 1608896152717277333, 38889412128248718215, 940014912175876488361, 22721558047666401897553, 549213840574693856578267

Offset: 1

Andrew Howroyd, Jun 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 3 of A286912.

Cf. A286911, A286913.

Empirical: a(n) = 20*a(n-1)+100*a(n-2)+24*a(n-3) -95*a(n-4)+10*a(n-5)+8*a(n-6) for n>6.

Empirical g.f.: x*(1 + 23*x + 9*x^2 - 41*x^3 + 2*x^4 + 8*x^5) / (1 - 20*x - 100*x^2 - 24*x^3 + 95*x^4 - 10*x^5 - 8*x^6). - Colin Barker, Jun 11 2017

A297205 Array read by antidiagonals: T(m,n) = number of edge covers in the m X n king graph.

Original entry on oeis.org

0, 1, 1, 1, 41, 1, 2, 1201, 1201, 2, 3, 36281, 559647, 36281, 3, 5, 1094401, 268870883, 268870883, 1094401, 5, 8, 33014921, 129026029705, 2058903341490, 129026029705, 33014921, 8, 13, 995960401, 61919807546309, 15748005991643285, 15748005991643285, 61919807546309, 995960401, 13

Offset: 1

Andrew Howroyd, Dec 26 2017

			Array begins:
========================================================================
m\n| 1       2            3                 4                      5
---|--------------------------------------------------------------------
1  | 0       1            1                 2                      3 ...
2  | 1      41         1201             36281                1094401 ...
3  | 1    1201       559647         268870883           129026029705 ...
4  | 2   36281    268870883     2058903341490      15748005991643285 ...
5  | 3 1094401 129026029705 15748005991643285 1919822469194024912961 ...
...

Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, King Graph

Main diagonal is A297056.

Cf. A286912.

cp's OEIS Frontend

A286913 Number of edge covers in the grid graph P_n X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A359993 Array read by antidiagonals: T(m,n) is the number of connected spanning subgraphs in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A286911 Number of edge covers in the ladder graph P_2 x P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A288025 Array read by antidiagonals: T(m,n) = number of minimal edge covers in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A284938 Triangle read by rows: coefficients of the edge cover polynomial for the n-path graph P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A288026 Array read by antidiagonals: T(m,n) = number of maximal matchings in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A288031 Number of edge covers in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A297205 Array read by antidiagonals: T(m,n) = number of edge covers in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs