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

1, 4, 16, 59, 214, 768, 2745, 9792, 34900, 124339, 442906, 1577540, 5618665, 20011452, 71272296, 253840779, 904068526, 3219889720, 11467810393, 40843217384, 145465283884, 518082304131, 1845177508818, 6571697181084, 23405446635913, 83359734391300, 296890096642144

Offset

1,2

Links

Paolo Xausa, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Fan Graph

Index entries for linear recurrences with constant coefficients, signature (4,0,-5,-2).

Formula

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

G.f.: x/((1 - x - x^2)*(1 - 3*x - 2*x^2)). - Stefano Spezia, Jun 29 2024

a(n) = A007483(n-1) - A212804(n). - R. J. Mathar, Jun 29 2024

Example

The fan graph F_{1,2} is the cycle with three vertices and has 4 edge covers.
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}.
We interpret F_{1,1} to be the path with two vertices with one edge cover.

Mathematica

LinearRecurrence[{4, 0, -5, -2}, {1, 4, 16, 59}, 30] (* Paolo Xausa, Jan 22 2025 *)

Crossrefs

Sequence in context: A047123 A297096 A330791 * A032094 A282083 A261563

Adjacent sequences: A374093 A374094 A374095 * A374097 A374098 A374099

Keyword

nonn,easy

Author

Feryal Alayont, Jun 28 2024

Status

approved