OFFSET
1,5
COMMENTS
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) + 12*3^(n-4) + 54*2^(n-4) + 108) for n != 4.
From Andrew Howroyd, Nov 23 2025: (Start)
E.g.f.: (x*exp(2*x) + 3*x)^4/6144.
G.f.: x^4*(1 - 90*x + 3805*x^2 - 100485*x^3 + 1859545*x^4 - 25645428*x^5 + 273700520*x^6 - 2317262880*x^7 + 15829053560*x^8 - 88249260480*x^9 + 404490721472*x^10 - 1529494237440*x^11 + 4768373773440*x^12 - 12191386398720*x^13 + 25277574236160*x^14 - 41723731623936*x^15 + 53317292359680*x^16 - 50613623193600*x^17 + 33481241395200*x^18 - 13759414272000*x^19 + 2641807540224*x^20)/((1 - 2*x)*(1 - 4*x)*(1 - 6*x)*(1 - 8*x))^5. (End)
EXAMPLE
a(6) = 6!/(2!2!2!2!)+6!*3/(3!3!) = 45+60 = 105; the first summand corresponds to the case of 2 two-node paths and 2 one-node paths; the second to the case of 1 three-node path and 3 one-node paths.
MATHEMATICA
A360276[n_] := Ceiling[n*(n-1)*(n-2)*(n-3)*2^(n-15)*(4^(n-4) + 12*3^(n-4) + 54*2^(n-4) + 108)/3];
Array[A360276, 25] (* Paolo Xausa, Jun 26 2026 *)
PROG
(PARI) a(n) = if(n==4, 1, n*(n-1)*(n-2)*(n-3)*2^(n-15)*(4^(n-4) + 12*3^(n-4) + 54*2^(n-4) + 108)/3) \\ Andrew Howroyd, Nov 23 2025
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Feb 01 2023
EXTENSIONS
a(1)=a(2)=0 prepended and a(4) corrected by Andrew Howroyd, Nov 23 2025
STATUS
approved