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

0, 0, 10, 105, 1015, 9625, 90972, 861420, 8191920, 78309000, 752317280, 7257522272, 70223986560, 680703296000, 6601793730560, 63984047339520, 619018056228864, 5972223901440000, 57415027394027520, 549677356175073280, 5238367168966328320, 49678823782558924800, 468783944069762252800

Offset

3,3

Comments

Although each path is self-avoiding, the different paths are allowed to intersect.

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.

Formula

a(n) = (1/3)*n*(n-1)*(n-2)*(n-3)*2^(n-15)*(4^(n-4) + 12*3^(n-4) + 54*2^(n-4) + 108) for n != 4.

Example

a(6) = 6!/(2!2!2!2!)+6!*3/(3!3!) = 45+60 = 105; the first summand corresponds to the case of 2 two-node paths and 2 one-node paths; the second to the case of 1 three-node path and 3 one-node paths.

Crossrefs

Cf. A001792, A359405 (unordered pairs of paths), A360021 (unordered triples of paths).

Sequence in context: A117832 A268763 A300850 * A210136 A068093 A260214

Adjacent sequences: A360273 A360274 A360275 * A360277 A360278 A360279

Keyword

nonn

Author

Ivaylo Kortezov, Feb 01 2023

Status

approved