A061705 - OEIS

%I #51 Sep 29 2023 21:00:04

%S 2,5,10,19,36,66,120,215,382,673,1178,2050,3550,6121,10514,17999,

%T 30720,52290,88788,150427,254342,429245,723190,1216514,2043386,

%U 3427661,5742490,9609355,16062492,26821698,44744688,74576735,124192270,206650201,343594514

%N Number of matchings in the wheel graph with n spokes.

%C Also the number of maximal matchings in the n-helm graph. - _Eric W. Weisstein_, May 27 2017

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).

%F G.f.: x*(2 + x - 2*x^2 - 2*x^3) / (1 - x - x^2)^2.

%F a(n) = (n+1)*Fibonacci(n) + 2*Fibonacci(n-1).

%F a(n) = sqrt(5)*((n+1)*(u^n - v^n) + 2*(u^(n-1) - v^(n-1)))/5, where u = (1+sqrt(5))/2, v = (1-sqrt(5))/2.

%F a(0)=2, a(1)=5, a(2)=10, a(3)=19; for n > 3, a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - _Harvey P. Dale_, Jun 05 2011

%F a(n) = n*Fibonacci(n) + Lucas(n) = (n+1)*Fibonacci(n+1) - (n-1)*Fibonacci(n-1). - _Bruno Berselli_, May 26 2015

%F a(n) = Sum_{k>=n-2} k*A000045(k)/(2^(k+3-n)). - _Diego Rattaggi_, Sep 21 2023

%e a(3)=10 because the matchings in a wheel graph with spokes OA, OB and OC are the empty set, {AB}, {BC}, {CA}, {OA}, {OB}, {OC}, {OA, BC}, {OB, CA}, {OC, AB}.

%t Rest[CoefficientList[Series[x (2 + x - 2 x^2 - 2 x^3)/(1 - x - x^2)^2, {x, 0, 40}], x]] (* _Harvey P. Dale_, Jun 05 2011 *)

%t LinearRecurrence[{2, 1, -2, -1}, {2, 5, 10, 19}, 40] (* _Harvey P. Dale_, Jun 05 2011 *)

%t Table[n Fibonacci[n] + LucasL[n], {n, 40}] (* _Eric W. Weisstein_, Mar 31 2017 *)

%o (Magma) [n*Fibonacci(n) + Lucas(n): n in [1..50]]; // _Vincenzo Librandi_, Jan 14 2016

%o (PARI) Vec(x*(2+x-2*x^2-2*x^3)/(1-x-x^2)^2 + O(x^50)) \\ _Colin Barker_, Mar 09 2016

%Y Cf. A000032, A000045.

%Y Cf. A258321 (Fibonacci(n) + n*Lucas(n)).

%K nonn,easy

%O 1,1

%A _Emeric Deutsch_, Jun 18 2001