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

Author

Feryal Alayont, Jun 28 2024

Keywords

• nonn
• easy

Examples

			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.
		

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).

Programs

Mathematica

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

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