A286945 -id:A286945 - cp's OEIS frontend

A284703 Number of maximal matchings in the n-prism graph.

1, 5, 10, 17, 51, 98, 211, 457, 964, 2095, 4489, 9638, 20723, 44469, 95550, 205225, 440777, 946808, 2033571, 4367947, 9381928, 20151345, 43283195, 92967814, 199685501, 428904403, 921243124, 1978737477, 4250128177, 9128846128, 19607840133, 42115660425

Offset: 1

Eric W. Weisstein, Apr 01 2017

nonn

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, May 16 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (1,2, 1,-1,2,1,-1,-1).

Cf. A284701, A286945, A284710, A102080, A068397, A123304.

I:=[1,5,10,17,51,98,211,457]; [n le 8 select I[n] else Self(n-1)+2*Self(n-2)+Self(n-3)-Self(n-4)+2*Self(n-5)+Self(n-6)-Self(n-7)-Self(n-8): n in [1..40]]; // Vincenzo Librandi, May 17 2017

LinearRecurrence[{1, 2, 1, -1, 2, 1, -1, -1}, {1, 5, 10, 17, 51, 98, 211, 457}, 40] (* Vincenzo Librandi, May 17 2017 *)
CoefficientList[Series[(-8 x^7 - 7 x^6 + 6 x^5 + 10 x^4 - 4 x^3 + 3 x^2 + 4 x + 1) / ((x^2 - x + 1) (x^3 - x - 1) (x^3 + 2 x^2 + x - 1)), {x, 0, 33}], x] (* Vincenzo Librandi, May 17 2017 *)
Table[2 Cos[n Pi/3] + RootSum[-1 - 2 # - #^2 + #^3 &, #^n &] +
  RootSum[-1 + #^2 + #^3 &, #^n &], {n, 20}] (* Eric W. Weisstein, May 17 2017 *)

Vec((-8*x^7-7*x^6+6*x^5+10*x^4-4*x^3+3*x^2+4*x+1)/((x^2-x+1)*(x^3-x-1)*(x^3+2*x^2+x-1))+O(x^20)) \\ Andrew Howroyd, May 16 2017

From Andrew Howroyd, May 16 2017 (Start)
a(n) = a(n-1)+2*a(n-2)+a(n-3)-a(n-4)+2*a(n-5)+a(n-6)-a(n-7)-a(n-8) for n>8.
G.f.: x*(-8*x^7-7*x^6+6*x^5+10*x^4 -4*x^3+3*x^2+4*x+1)/((x^2-x+1)*(x^3-x-1)*(x^3+2*x^2+x-1)).
(End)

a(1)-a(2) and a(20)-a(32) from Andrew Howroyd, May 16 2017

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.

A287595 Number of maximal matchings in the n X n grid graph.

Original entry on oeis.org

1, 1, 2, 22, 400, 22228, 3136370, 1158560776, 1147204164108, 2980178704765860, 20513821200001569410, 373243563814532182524614, 17941038966060235808302667164

Offset: 0

Eric W. Weisstein, May 27 2017

Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Main diagonal of A288026.

Cf. A286945, A288028, A099390, A242861, A284703.

Join[{1}, Table[Length@FindIndependentVertexSet[LineGraph@GridGraph[{n, n}], Infinity, All], {n, 2, 6}]] (* Eric W. Weisstein, Jul 13 2024 *)

a(7)-a(10) from Andrey Zabolotskiy, May 31 2017
a(1) changed and a(0) prepended by Alois P. Heinz, May 31 2017
a(11)-a(12) from Andrew Howroyd, Jun 04 2017

A288028 Number of maximal matchings in the grid graph P_3 X P_n.

Original entry on oeis.org

2, 5, 22, 75, 264, 941, 3286, 11623, 40960, 144267, 508812, 1792981, 6319994, 22277291, 78518760, 276763545, 975517878, 3438444583, 12119670866, 42718700667, 150572583140, 530730064095, 1870688029160, 6593699432859, 23241110692298, 81918995835971

Offset: 1

Andrew Howroyd, Jun 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.

Row 3 of A288026.

Cf. A286945, A287595.

Empirical: a(n) = a(n-1) +5*a(n-2) +11*a(n-3) +5*a(n-4) +14*a(n-5) +8*a(n-6) +3*a(n-7) -5*a(n-9) -11*a(n-10) -a(n-11) +2*a(n-12) +a(n-15) for n>15.

Empirical g.f.: x*(2 +3*x +7*x^2 +6*x^3 +14*x^4 +7*x^5 +4*x^6 -x^7 -5*x^8 - 11*x^9 -2*x^10 +2*x^11 +x^12 +x^14)/(1 -x -5*x^2 -11*x^3 -5*x^4 -14*x^5 - 8*x^6 -3*x^7 +5*x^9 +11*x^10 +x^11 -2*x^12 -x^15). - Colin Barker, Jun 11 2017

cp's OEIS Frontend

A284703 Number of maximal matchings in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

A287595 Number of maximal matchings in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A288028 Number of maximal matchings in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula