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

3, 15, 70, 330, 1596, 7840, 38592, 188640, 911680, 4350720, 20507136, 95560192, 440724480, 2014003200, 9128476672, 41074384896, 183618256896, 816062464000, 3607813816320, 15874289958912, 69544309424128, 303465643376640, 1319414897049600, 5717462509158400, 24699433622962176, 106397550709309440

Offset

3,1

Comments

The paths considered here have segments that do not intersect each other. Although each path is self-avoiding, the different paths are allowed to intersect.

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

Links

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

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 (18,-132,504,-1056,1152,-512).

Formula

a(n) = n * (n-1) * 2^(n-6) * (2^(n-3) + 3).

From Stefano Spezia, Dec 30 2022: (Start)

G.f.: x^3*(3 - 39*x + 196*x^2 - 462*x^3 + 504*x^4 - 224*x^5) / ((1 - 2*x)^3*(1 - 4*x)^3).

a(n) = 18*a(n-1) - 132*a(n-2) + 504*a(n-3) - 1056*a(n-4) + 1152*a(n-5) - 512*a(n-6) for n > 8. (End)

E.g.f.: ((x*exp(2*x) + 3*x)/4)^2/2 - x^2/2. - Andrew Howroyd, Jan 10 2023

Mathematica

LinearRecurrence[{18, -132, 504, -1056, 1152, -512}, {3, 15, 70, 330, 1596, 7840}, 26] (* Stefano Spezia, Dec 30 2022 *)

Prog

(PARI) a(n) = {if(n < 3, 0, n*(n - 1)*2^(n-6)*(2^(n-3) + 3))} \\ Andrew Howroyd, Jan 10 2023

Crossrefs

A332426 is the case with paths having at least 2 nodes each.

Cf. A001792.

Sequence in context: A245751 A033876 A291031 * A009174 A178345 A183547

Adjacent sequences: A359402 A359403 A359404 * A359406 A359407 A359408

Keyword

nonn,easy

Author

Ivaylo Kortezov, Dec 30 2022

Status

approved