A061705 Number of matchings in the wheel graph with n spokes.

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

Colin Barker, Table of n, a(n) for n = 1..1000

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

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

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. A000032, A000045.

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

Sequence in context: A288579 A065613 A249557 * A052944 A132736 A263366

Adjacent sequences: A061702 A061703 A061704 * A061706 A061707 A061708

Keyword

nonn,easy

Author

Emeric Deutsch, Jun 18 2001

Status

approved