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,2

Links

Table of n, a(n) for n=3..25.

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) + 3*2^(n-3) + 9) for n >= 4.

Example

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.

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

Prog

(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

Crossrefs

Cf. A359405 (unordered pairs).

Sequence in context: A297645 A201191 A214982 * A189801 A024077 A097129

Adjacent sequences: A360018 A360019 A360020 * A360022 A360023 A360024

Keyword

nonn,easy

Author

Ivaylo Kortezov, Jan 22 2023

Status

approved