OFFSET
1,6
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 = 1..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) for n > 3.
E.g.f.: (1/6)*((x*exp(2*x) - x)/4)^3. - Andrew Howroyd, Jan 10 2023
From Andrew Howroyd, Nov 23 2025: (Start)
Inverse binomial transform of A361284.
G.f.: 3*x^6*(1 - 3*x)*(5 - 120*x + 1200*x^2 - 6480*x^3 + 20560*x^4 - 39360*x^5 + 45440*x^6 - 30720*x^7 + 9216*x^8)/((1 - 2*x)*(1 - 4*x)*(1 - 6*x))^4. (End)
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
EXTENSIONS
a(1)-a(3)=0 prepended by Andrew Howroyd, Nov 23 2025
STATUS
approved