A360021 - OEIS

%I #17 Feb 11 2023 20:31:58

%S 1,6,45,315,2205,15624,111888,807840,5868720,42799680,312504192,

%T 2278418688,16549827840,119567831040,858293084160,6118081708032,

%U 43298650386432,304260332175360,2123395686236160,14722247331348480,101446590051975168,695007859780878336,4735844958575001600

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

%H Ivaylo Kortezov, <a href="https://doi.org/10.53656/math2022-6-4-set">Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon</a>, Mathematics and Informatics, Vol. 65, No. 6, 2022.

%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (48,-1040,13440,-115296,691200,-2967296,9185280,-20336896,31395840,-32071680,19464192,-5308416).

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

%e 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.

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

%o (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

%Y Cf. A359405 (unordered pairs).

%K nonn,easy

%O 3,2

%A _Ivaylo Kortezov_, Jan 22 2023