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

Author

Ivaylo Kortezov, Dec 30 2022

Keywords

• nonn
• easy

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

• 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).

Crossrefs

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

Cf. A001792.

Programs

Mathematica

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

PARI

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

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