A284709 Number of maximal matchings in the wheel graph on n nodes.
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
Links
- Colin Barker, Table of n, a(n) for n = 1..1000
- 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
- Index entries for linear recurrences with constant coefficients, signature (0,3,2,-3,-4,0,2,1).
Crossrefs
Cf. A000931.
Programs
-
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 *) -
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
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
Comments