login
A061705
Number of matchings in the wheel graph with n spokes.
3
2, 5, 10, 19, 36, 66, 120, 215, 382, 673, 1178, 2050, 3550, 6121, 10514, 17999, 30720, 52290, 88788, 150427, 254342, 429245, 723190, 1216514, 2043386, 3427661, 5742490, 9609355, 16062492, 26821698, 44744688, 74576735, 124192270, 206650201, 343594514
OFFSET
1,1
COMMENTS
Also the number of maximal matchings in the n-helm graph. - Eric W. Weisstein, May 27 2017
LINKS
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
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
G.f.: x*(2 + x - 2*x^2 - 2*x^3) / (1 - x - x^2)^2.
a(n) = (n+1)*Fibonacci(n) + 2*Fibonacci(n-1).
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.
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
a(n) = n*Fibonacci(n) + Lucas(n) = (n+1)*Fibonacci(n+1) - (n-1)*Fibonacci(n-1). - Bruno Berselli, May 26 2015
a(n) = Sum_{k>=n-2} k*A000045(k)/(2^(k+3-n)). - Diego Rattaggi, Sep 21 2023
EXAMPLE
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}.
MATHEMATICA
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 *)
LinearRecurrence[{2, 1, -2, -1}, {2, 5, 10, 19}, 40] (* Harvey P. Dale, Jun 05 2011 *)
Table[n Fibonacci[n] + LucasL[n], {n, 40}] (* Eric W. Weisstein, Mar 31 2017 *)
PROG
(Magma) [n*Fibonacci(n) + Lucas(n): n in [1..50]]; // Vincenzo Librandi, Jan 14 2016
(PARI) Vec(x*(2+x-2*x^2-2*x^3)/(1-x-x^2)^2 + O(x^50)) \\ Colin Barker, Mar 09 2016
CROSSREFS
Cf. A258321 (Fibonacci(n) + n*Lucas(n)).
Sequence in context: A288579 A065613 A249557 * A052944 A132736 A263366
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jun 18 2001
STATUS
approved