OFFSET
4,1
COMMENTS
Paths must have at least two nodes.
The number of non-selfintersecting paths that cover all vertices of a convex n-gon is given by A001792(n-2).
LINKS
Index entries for linear recurrences with constant coefficients, signature (10,-40,80,-80,32).
FORMULA
a(n) = (1/3)*n*(n-1)*(n-3)*(n+4)*2^(n-8).
From Stefano Spezia, Feb 12 2020: (Start)
O.g.f.: x^4*(-2 + 5*x - 5*x^2 + 2*x^3)/(-1 + 2*x)^5.
E.g.f.: x^2*(3 + exp(2*x)*(-3 + 6*x + 2*x^2))/96.
a(n) = 10*a(n-1) - 40*a(n-2) + 80*a(n-3) - 80*a(n-4) + 32*a(n-5) for n > 8.
(End)
EXAMPLE
a(5) = 15 since one of the non-selfintersecting paths has to be a segment connecting two adjacent vertices (5 choices) and the other path will connect the remaining vertices in one of three ways.
MAPLE
gf := x^2*(3 + exp(2*x)*(-3 + 6*x + 2*x^2))/96: ser := series(gf, x, 36):
seq(n!*coeff(ser, x, n), n=4..30); # Peter Luschny, Mar 01 2020
MATHEMATICA
Array[(1/3) # (# - 1) (# - 3) (# + 4)*2^(# - 8) &, 27, 4] (* Michael De Vlieger, Feb 25 2020 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Ivaylo Kortezov, Feb 12 2020
STATUS
approved