A374096 - OEIS

%I #18 Jun 29 2024 17:26:48

%S 1,4,16,59,214,768,2745,9792,34900,124339,442906,1577540,5618665,

%T 20011452,71272296,253840779,904068526,3219889720,11467810393,

%U 40843217384,145465283884,518082304131,1845177508818,6571697181084,23405446635913,83359734391300,296890096642144

%N Number of edge covers of fan graph F_{1,n}.

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

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

%F a(n) = 4*a(n-1)-5*a(n-3)-2*a(n-4).

%F G.f.: x/((1 - x - x^2)*(1 - 3*x - 2*x^2)). - _Stefano Spezia_, Jun 29 2024

%F a(n) = A007483(n-1) - A212804(n). - _R. J. Mathar_, Jun 29 2024

%e The fan graph F_{1,2} is the cycle with three vertices and has 4 edge covers.

%e The graph F_{1,3} is formed by adding a chord to the cycle with four vertices. The cycle C_4 has 7 edge covers, so there are 7 edge covers of F_{1,3} without the chord. If the chord is there, the two endpoints are covered. To cover the remaining two vertices, we need at least one of the two edges on each side of each vertex, giving us 3*3 choices total. So we have 16 edge covers for F_{1,3}.

%e We interpret F_{1,1} to be the path with two vertices with one edge cover.

%K nonn,easy

%O 1,2

%A _Feryal Alayont_, Jun 28 2024