login
A359404
Number of unordered triples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.
4
0, 0, 15, 315, 4200, 45360, 433440, 3825360, 31944000, 256164480, 1991877888, 15117822720, 112519680000, 824063385600, 5953789181952, 42518284701696, 300588079104000, 2106258635980800, 14642876032942080, 101081482775691264, 693338799538176000, 4728258324725760000, 32074214121878323200
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
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
Cf. A001792, A332426 (unordered pairs of paths).
Sequence in context: A284070 A133766 A347980 * A289951 A112489 A062757
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Dec 30 2022
STATUS
approved