A286945 Number of maximal matchings in the ladder graph P_2 X P_n.

1, 2, 5, 11, 24, 51, 109, 234, 503, 1081, 2322, 4987, 10711, 23006, 49415, 106139, 227976, 489669, 1051759, 2259072, 4852259, 10422163, 22385754, 48082339, 103276009, 221826440, 476460797, 1023389687, 2198137722, 4721377893, 10141043023, 21781936530

Offset

1,2

Links

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

Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.

Eric Weisstein's World of Mathematics, Ladder Graph

Eric Weisstein's World of Mathematics, Matching

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Index entries for linear recurrences with constant coefficients, signature (2,0,0,1,1).

Formula

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

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

Maple

seq(coeff(series(x*(1+x^2+x^3+x^4)/(1-2*x-x^4-x^5), x, n+1), x, n), n = 1..35); # G. C. Greubel, Dec 30 2019

Mathematica

Table[3Cos[nPi/3]/13 - 5Sin[nPi/3]/(13 Sqrt[3]) + RootSum[-1 -2# -#^2 +#^3 &, (-6 -72# +80#^2) #^n &]/403, {n, 35}] (* Eric W. Weisstein, Jul 13 2017 *)
LinearRecurrence[{2, 0, 0, 1, 1}, {1, 2, 5, 11, 24}, 35] (* Eric W. Weisstein, Jul 13 2017 *)
CoefficientList[Series[(1+x^2+x^3+x^4)/(1-2x-x^4-x^5), {x, 0, 35}], x] (* Eric W. Weisstein, Jul 13 2017 *)

Prog

(PARI) Vec((1+x^2+x^3+x^4)/((1-x+x^2)*(1-x-2*x^2-x^3)) + O(x^35))
(Magma) R<x>:=PowerSeriesRing(Integers(), 35); Coefficients(R!( x*(1+x^2+x^3+x^4)/(1-2*x-x^4-x^5) )); // G. C. Greubel, Dec 30 2019
(Sage)
def A286945_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( x*(1+x^2+x^3+x^4)/(1-2*x-x^4-x^5) ).list()
a=A286945_list(35); a[1:] # G. C. Greubel, Dec 30 2019
(GAP) a:=[1, 2, 5, 11, 24];; for n in [6..35] do a[n]:=2*a[n-1]+a[n-4]+a[n-5]; od; a; # G. C. Greubel, Dec 30 2019

Crossrefs

Cf. A284703, A284710, A286911.

Sequence in context: A027934 A336482 A134389 * A371797 A350326 A111297

Adjacent sequences: A286942 A286943 A286944 * A286946 A286947 A286948

Keyword

nonn

Author

Andrew Howroyd, May 16 2017

Status

approved