A374450 Number of edge covers of the fan graph F_{n,4}.

59, 1289, 23123, 376913, 5875499, 89719769, 1357012163, 20434006433, 307062808859, 4609813953449, 69174320548403, 1037804612461553, 15568397893099019, 233535269569297529, 3503094152437895843, 52546868050923710273, 788206211120541289979, 11823115499323514984009, 177346888817516282750483

Offset

1,1

Comments

Label vertices of F_{n,4} with v1, ..., v_n, a, b, c, d with be adjacent to a and c and d adjacent to 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 15 ways to connect to vertices a, b, c, d. Once we connect all v_i's, we then have 8 options for the edges ab, bc, and cd to exist or not, giving 8*15^n options. But not all of these will be an edge cover. For example, if all v_i's connect to only b and c, we have to add edges ab and cd in the second step. So, 12*7^n options are removed. However, we removed too many options here. This line of reasoning continues, following the Inclusion-Exclusion Principle, to obtain the remaining pieces of the formula for a(n).

Links

Table of n, a(n) for n=1..19.

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 (26,-196,486,-315).

Formula

a(n) = 8*15^n - 12*7^n + 9*3^n - 4.

From Stefano Spezia, Jul 08 2024: (Start)

G.f.: x*(59 - 245*x + 1173*x^2 - 315*x^3)/((1 - x)*(1 - 3*x)*(1 - 7*x)*(1 - 15*x)).

E.g.f.: 8*exp(15*x) - 12*exp(7*x) + 9*exp(3*x) - 4*exp(x) - 1. (End)

Prog

(Python)
def a_n(n):
    return 8 * 15**n - 12*7^n + 9 * 3**n + 3

Crossrefs

Cf. A100774, A373293, A374096.

Sequence in context: A248974 A245941 A248620 * A210398 A278366 A134652

Adjacent sequences: A374447 A374448 A374449 * A374451 A374452 A374453

Keyword

nonn,easy

Author

Marshall Nicholson, Jul 08 2024

Status

approved