login
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
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
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
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Dec 30 2022
STATUS
approved