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
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
KEYWORD
nonn,easy
AUTHOR
Marshall Nicholson, Jul 08 2024
STATUS
approved