OFFSET
4,3
COMMENTS
The paths considered here cover at least 2 vertices and have segments that do not intersect each other. Although each path is self-avoiding, the different paths are allowed to intersect.
The number of self-avoiding paths that cover all vertices of a convex n-gon is given by A001792(n-2).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 4..500
Ivaylo Kortezov, Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon, Mathematics and Informatics, Vol. 65, No. 6, 2022.
Index entries for linear recurrences with constant coefficients, signature (48,-1040,13440,-115296,691200,-2967296,9185280,-20336896,31395840, -32071680,19464192,-5308416).
FORMULA
a(n) = n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1).
E.g.f.: (1/6)*((x*exp(2*x) - x)/4)^3. - Andrew Howroyd, Jan 10 2023
EXAMPLE
a(6) = 6!/(2!2!2!3!) = 5*3 = 15 is the number of ways to pair each vertex with another.
a(7) = 7!*3/(2!*2!*3!*2!) = 315 since the 7 vertices must be split into two pairs and one triple, the order of the two pairs is irrelevant, and there are 3 choices of the segment in the triple not connected by a segment.
MATHEMATICA
Table[n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1), {n, 4, 26}] (* Stefano Spezia, Dec 30 2022 *)
PROG
(PARI) a(n) = {if(n<=3, 0, n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1))} \\ Andrew Howroyd, Jan 10 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Dec 30 2022
STATUS
approved