A360021 Number of unordered triples of self-avoiding paths with nodes that cover all vertices of a convex n-gon; one-node paths are allowed.

1, 6, 45, 315, 2205, 15624, 111888, 807840, 5868720, 42799680, 312504192, 2278418688, 16549827840, 119567831040, 858293084160, 6118081708032, 43298650386432, 304260332175360, 2123395686236160, 14722247331348480, 101446590051975168, 695007859780878336, 4735844958575001600

Offset: 3

Author

Ivaylo Kortezov, Jan 22 2023

Keywords

• nonn
• easy

Examples

			a(5) = 5!/(2!2!2!) + binomial(5,2)*3 = 15 + 30 = 45; the first summand corresponds to the case when two of the paths have two nodes each and one path has one node; the second corresponds to the case when two of the paths have one node each and one path has three nodes.
		

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

Crossrefs

Cf. A359405 (unordered pairs).

Programs

Mathematica

LinearRecurrence[{48,-1040,13440,-115296,691200,-2967296,9185280,-20336896,31395840,-32071680,19464192,-5308416},{1,6,45,315,2205,15624,111888,807840,5868720,42799680,312504192,2278418688,16549827840},23] (* Stefano Spezia, Jan 22 2023 *)

PARI

a(n) = if(n==3, 1, n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) + 3*2^(n-3) + 9)) \\ Andrew Howroyd, Jan 23 2023

Formula

a(n) = n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) + 3*2^(n-3) + 9) for n >= 4.