A360275 Number of unordered quadruples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

0, 0, 0, 0, 0, 105, 3780, 81900, 1386000, 20207880, 266666400, 3277354080, 38198160000, 427365818880, 4629059635200, 48842864179200, 504335346278400, 5114054709319680, 51064119467827200, 503151159589478400, 4900668252598272000, 47248486914198011904, 451429610841538560000

Offset

3,6

Comments

The paths considered here cover at least 2 vertices. 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) - 4*3^(n-4) + 6*2^(n-4) - 4) for n != 4.

Example

a(9) = 9!*3/(2!2!2!3!3!) = 3780 since we have to split the 9 vertices into three pairs and one triple, the order of the three pairs is irrelevant, and there are 3 ways of connecting the triple.

Crossrefs

Cf. A001792, A332426 (unordered pairs of paths), A359404 (unordered triples of paths).

Sequence in context: A289952 A112490 A006361 * A221791 A210138 A075350

Adjacent sequences: A360272 A360273 A360274 * A360276 A360277 A360278

Keyword

nonn

Author

Ivaylo Kortezov, Feb 01 2023

Status

approved