login
Number of maximal matchings in the n-gear graph.
2

%I #12 Nov 23 2024 03:34:41

%S 3,6,11,22,47,98,198,394,776,1512,2917,5582,10610,20050,37697,70562,

%T 131565,244460,452829,836482,1541318,2833624,5198692,9519722,17402027,

%U 31759964,57878498,105331522,191445503,347548382,630235055,1141662370,2066086475

%N Number of maximal matchings in the n-gear graph.

%C Extended to a(1)-a(2) using the formula/recurrence.

%H Colin Barker, <a href="/A287425/b287425.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GearGraph.html">Gear Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentEdgeSet.html">Maximal Independent Edge Set</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,12,-11,7,-3,1).

%F G.f.: x*(3 - 9*x + 11*x^2 - 9*x^3 + 8*x^4 - 4*x^5 + 2*x^6) / ((1 - x)*(1 - 2*x + x^2 - x^3)^2). - _Colin Barker_, May 25 2017

%t LinearRecurrence[{5, -10, 12, -11, 7, -3, 1}, {3, 6, 11, 22, 47, 98, 198}, 30]

%t CoefficientList[Series[(-3 + 9 x - 11 x^2 + 9 x^3 - 8 x^4 + 4 x^5 - 2 x^6)/((-1 + x) (-1 + 2 x - x^2 + x^3)^2), {x, 0, 20}], x] (* _Eric W. Weisstein_, Dec 30 2017 *)

%t Table[2 - n RootSum[-1 + # - 2 #^2 + #^3 &, 6 #^(n + 1) - 11 #^(n + 2) + 2 #^(n + 3) &]/23, {n, 20}] (* _Eric W. Weisstein_, Dec 30 2017 *)

%o (PARI) Vec(x*(3 - 9*x + 11*x^2 - 9*x^3 + 8*x^4 - 4*x^5 + 2*x^6) / ((1 - x)*(1 - 2*x + x^2 - x^3)^2) + O(x^40)) \\ _Colin Barker_, May 25 2017

%K nonn,easy,changed

%O 1,1

%A _Eric W. Weisstein_, May 24 2017