A288025 -id:A288025 - cp's OEIS frontend

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

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.

A288027 Number of minimal edge covers in the grid graph P_n X P_n.

Original entry on oeis.org

0, 2, 38, 1834, 419710, 356269056, 1163645044100, 15000387107144576, 749707067231291403016

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.

			In the 3 X 3 grid, the minimal edge covers up to rotation and reflection are:
.__.__.    .__.__.    .__.__.    .__.__.    .__.__.    .__.  .
.__.__.    .  .  .    .__.  .    .  .__.    .  |  .    .  |  |
.__.__.    |  |  |    .__.  |    |__.  |    |  .__|    |  .__.
The first two of these need to be counted 2 and 4 times and the rest which have no symmetry 8 times so a(3) = 38.

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Main diagonal of A288025.

Cf. A286913.

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

A288029 Number of minimal edge covers in the ladder graph P_2 X P_n.

Original entry on oeis.org

1, 2, 6, 17, 45, 120, 324, 873, 2349, 6322, 17018, 45809, 123305, 331904, 893400, 2404801, 6473097, 17423890, 46900574, 126244129, 339816309, 914696984, 2462126012, 6627401865, 17839239445, 48018585634, 129253524146, 347916817697, 936501444241, 2520817938240

Offset: 1

Andrew Howroyd, Jun 04 2017

nonn

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

Row 2 of A288025.

Cf. A288030, A288027.

Table[(RootSum[1 - 2 #^2 - 2 #^3 + #^4 &, 94 #^n + 33 #^(n + 1) - 7 #^(n + 2) + 8 #^(n + 3) &] + 182 (2 Cos[n Pi/2] + Sin[n Pi/2]))/910, {n, 20}] (* Eric W. Weisstein, Aug 03 2017 *)
LinearRecurrence[{2, 1, 2, 1, 0, -1}, {1, 2, 6, 17, 45, 120}, 20] (* Eric W. Weisstein, Aug 03 2017 *)
CoefficientList[Series[(1 + x^2 + x^3 - x^5)/(1 - 2 x - x^2 - 2 x^3 - x^4 + x^6), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 03 2017 *)

Vec((1+x^2+x^3-x^5)/((1+x^2)*(1-2*x-2*x^2+x^4))+O(x^20))

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

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

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

Original entry on oeis.org

1, 6, 38, 190, 1021, 5494, 29042, 154772, 824695, 4386942, 23356322, 124344111, 661873859, 3523418150, 18756407661, 99845472493, 531509598443, 2829393615575, 15061734439895, 80178331797652, 426814323111204, 2272065745374039, 12094915689644237

Offset: 1

Andrew Howroyd, Jun 04 2017

nonn

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

Row 3 of A288025.

Cf. A288029, A288027.

Empirical: a(n) = 3*a(n-1)+6*a(n-2)+35*a(n-3) -7*a(n-4)+15*a(n-5)-55*a(n-6) +31*a(n-7)+36*a(n-8)+36*a(n-9) -124*a(n-10)-8*a(n-12)+32*a(n-13) +a(n-14)+9*a(n-15)-2*a(n-16) -2*a(n-17)-a(n-18) for n>18.

Empirical g.f.: x*(1 + 3*x + 14*x^2 + 5*x^3 + 20*x^4 - 12*x^5 + 15*x^6 + 6*x^7 + 2*x^8 - 82*x^9 - 5*x^10 - 3*x^11 + 29*x^12 + 8*x^14 - 2*x^15 - 2*x^16 - x^17) / (1 - 3*x - 6*x^2 - 35*x^3 + 7*x^4 - 15*x^5 + 55*x^6 - 31*x^7 - 36*x^8 - 36*x^9 + 124*x^10 + 8*x^12 - 32*x^13 - x^14 - 9*x^15 + 2*x^16 + 2*x^17 + x^18). - Colin Barker, Jun 16 2017

cp's OEIS Frontend

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

A288027 Number of minimal edge covers in the grid graph P_n X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A288029 Number of minimal edge covers in the ladder graph P_2 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula