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

Author

Andrew Howroyd, May 16 2017

Keywords

• nonn

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).

Crossrefs

Cf. A284703, A284710, A286911.

Programs

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

Magma

R:=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

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 *)

PARI

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

Sage

def A286945_list(prec):
    P. = 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

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)).