A359404 - OEIS

%I #23 Jan 29 2023 23:01:19

%S 0,0,15,315,4200,45360,433440,3825360,31944000,256164480,1991877888,

%T 15117822720,112519680000,824063385600,5953789181952,42518284701696,

%U 300588079104000,2106258635980800,14642876032942080,101081482775691264,693338799538176000,4728258324725760000,32074214121878323200

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

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

%C The number of self-avoiding paths that cover all vertices of a convex n-gon is given by A001792(n-2).

%H Andrew Howroyd, <a href="/A359404/b359404.txt">Table of n, a(n) for n = 4..500</a>

%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) - 2^(n-3) + 1).

%F E.g.f.: (1/6)*((x*exp(2*x) - x)/4)^3. - _Andrew Howroyd_, Jan 10 2023

%e a(6) = 6!/(2!2!2!3!) = 5*3 = 15 is the number of ways to pair each vertex with another.

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

%t Table[n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1),{n,4,26}] (* _Stefano Spezia_, Dec 30 2022 *)

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

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

%K nonn,easy

%O 4,3

%A _Ivaylo Kortezov_, Dec 30 2022