OFFSET
1,8
COMMENTS
The paths considered here cover at least 2 vertices. Although each path is self-avoiding, the different paths are allowed to intersect.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..500
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 (100,-4700,138000,-2837920, 43433600,-513123200,4789824000, -35865826560,217466393600,-1073110707200, 4315394560000, -14111810519040,37306980761600, -78925181747200,131514105856000, -168508973383680,159964043673600, -105817256755200,43486543872000,-8349416423424).
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.
From Andrew Howroyd, Nov 23 2025: (Start)
E.g.f.: (1/24)*((x*exp(2*x) - x)/4)^4.
G.f.: 3*x^8*(35 - 2240*x + 65800*x^2 - 1176000*x^3 + 14293160*x^4 - 125104000*x^5 + 814775360*x^6 - 4024384000*x^7 + 15231717760*x^8 - 44359168000*x^9 + 99315865600*x^10 - 169941811200*x^11 + 219412725760*x^12 - 208286515200*x^13 + 137782886400*x^14 - 56623104000*x^15 + 10871635968*x^16)/((1 - 2*x)*(1 - 4*x)*(1 - 6*x)*(1 - 8*x))^5. (End)
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.
MATHEMATICA
A360275[n_] := Ceiling[n*(n-1)*(n-2)*(n-3)*2^(n-15)*(4^(n-4) - 4*3^(n-4) + 6*2^(n-4) - 4)/3];
Array[A360275, 25] (* Paolo Xausa, Jun 26 2026 *)
PROG
(PARI) a(n) = if(n < 8, 0, n*(n-1)*(n-2)*(n-3)*2^(n-15)*(4^(n-4) - 4*3^(n-4) + 6*2^(n-4) - 4)/3) \\ Andrew Howroyd, Nov 23 2025
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Ivaylo Kortezov, Feb 01 2023
EXTENSIONS
a(1)=a(2)=0 prepended by Andrew Howroyd, Nov 23 2025
STATUS
approved