A373293 Number of edge covers of the fan graph F_{n,3}.

16, 154, 1240, 9202, 66016, 466954, 3283240, 23026402, 161316016, 1129605754, 7908421240, 55362491602, 387548070016, 2712868376554, 18990174295240, 132931507044802, 930521410248016, 6513652454539354, 45595574930185240, 319169047756526002

Offset: 1

Author

Feryal Alayont, Jun 22 2024

Keywords

• nonn
• easy

Comments

Label vertices of F_{n,3} with v1, ..., v_n, a, b, c, with b adjacent to both a and c. An edge cover is a subset of the edges so that each vertex is the endpoint of at least one edge. Each of the n vertices has 7 ways to connect to vertices a, b, c. Once we connect all v_i's, we then have 4 options for the edges ab and bc to exist or not, giving 4*7^m options. But not all of these will be an edge cover. For example, if all v_i's connected to a and b only, we have to add edge bc in the second step. So 5*3^m are removed. But we removed 3 cases where all v_i's connected to only a, or only b, or only c too many times.

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Edge Cover.
• Eric Weisstein's World of Mathematics, Fan Graph.
• Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Crossrefs

Cf. A100774 (in F_{n,2}).

Programs

Mathematica

A373293[n_] := 4*7^n - 5*3^n + 3; Array[A373293, 25] (* or *)
LinearRecurrence[{11, -31, 21}, {16, 154, 1240}, 25] (* Paolo Xausa, Jun 24 2024 *)

Python

def a_n(n):
    return 4 * 7**n - 5 * 3**n + 3

Formula

a(n) = 4*7^n - 5*3^n + 3.

From Stefano Spezia, Jun 24 2024: (Start)

G.f.: 2*x*(8 - 11*x + 21*x^2)/((1 - x)*(1 - 3*x)*(1 - 7*x)).

E.g.f.: 4*exp(7*x) - 5*exp(3*x) + 3*exp(x) - 2. (End)