login
A286945
Number of maximal matchings in the ladder graph P_2 X P_n.
5
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
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
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
KEYWORD
nonn
AUTHOR
Andrew Howroyd, May 16 2017
STATUS
approved