login
A284709
Number of maximal matchings in the wheel graph on n nodes.
2
2, 1, 4, 3, 10, 10, 20, 28, 42, 63, 92, 132, 194, 273, 394, 555, 786, 1105, 1550, 2166, 3022, 4200, 5832, 8073, 11162, 15400, 21218, 29187, 40098, 55013, 75392, 103199, 141122, 192786, 263128, 358820, 488918, 665667, 905656, 1231308, 1672962, 2271605
OFFSET
1,1
COMMENTS
Linear recurrence used to extrapolate to a(1), a(2), a(3).
LINKS
Tomislav Doslic, I. Zubac, Counting maximal matchings in linear polymers, Ars Mathematica Contemporanea 11 (2016) 255-276. See Prop. 7.2.
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Wheel Graph
FORMULA
a(n) = 3*a(n-2) + 2*a(n-3) - 3*a(n-4) - 4*a(n-5) + 2*a(n-7) + a(n-8).
G.f.: (x*(-2 - x + 2*x^2 + 4*x^3 - 2*x^4 - 4*x^5 + x^7))/((-1 + x^2)*(-1 + x^2 + x^3)^2).
a(n) = (n-1)*Padovan(n+3)+1-(-1)^n, where Padovan(k) = A000931(k). (Eee Doslic et al.) - N. J. A. Sloane, Apr 24 2017
MAPLE
A000931 := proc(n) option remember; if n = 0 then 1 elif n <= 2 then 0 else procname(n-2)+procname(n-3); fi; end;
psi:=n->A000931(n+6);
f:=n->n*psi(n-2)+1+(-1)^n;
[seq(f(n), n=0..40)]; # Produces the sequence with an offset of 0 - N. J. A. Sloane, Apr 24 2017
MATHEMATICA
LinearRecurrence[{0, 3, 2, -3, -4, 0, 2, 1}, {2, 1, 4, 3, 10, 10, 20, 28, 42, 63, 92}, 37] (* Eric W. Weisstein, Apr 01 2017 *)
Padovan[n_] := RootSum[-1 - # + #^3 &, 5 #^n - 6 #^(n + 1) + 4 #^(n + 2) &]/23; Table[(n - 1) Padovan[n + 3] - (-1)^n + 1, {n, 20}] (* Eric W. Weisstein, Dec 30 2017 *)
CoefficientList[Series[(-2 - x + 2 x^2 + 4 x^3 - 2 x^4 - 4 x^5 + x^7)/((-1 + x^2) (-1 + x^2 + x^3)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Dec 30 2017 *)
PROG
(PARI) Vec(x*(2 + x - 2*x^2 - 4*x^3 + 2*x^4 + 4*x^5 - x^7) / ((1 - x)*(1 + x)*(1 - x^2 - x^3)^2) + O(x^50)) \\ Colin Barker, Apr 25 2017
CROSSREFS
Cf. A000931.
Sequence in context: A109195 A258310 A217927 * A307365 A032662 A185413
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Apr 01 2017
STATUS
approved