A359404 Number of unordered triples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

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

Author

Ivaylo Kortezov, Dec 30 2022

Keywords

• nonn
• easy

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).

Examples

			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.
		

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).

Crossrefs

Cf. A001792, A332426 (unordered pairs of paths).

Programs

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 *)

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

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