OFFSET
1,4
COMMENTS
Although each path is self-avoiding, the different paths are allowed to intersect.
LINKS
Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.
Index entries for linear recurrences with constant coefficients, signature (27,-312,2016,-7986,19998,-31472,29880,-15525,3375).
FORMULA
a(n) = n*(n-1)*2^(-5)*(5^(n-2) - 2*3^(n-2) + 1).
From Andrew Howroyd, Feb 19 2023: (Start)
Binomial transform of A332426.
a(n) = 27*a(n-1) - 312*a(n-2) + 2016*a(n-3) - 7986*a(n-4) + 19998*a(n-5) - 31472*a(n-6) + 29880*a(n-7) - 15525*a(n-8) + 3375*a(n-9) for n > 9.
G.f.: x^4*(3 - 36*x + 156*x^2 - 288*x^3 + 197*x^4)/((1 - x)*(1 - 3*x)*(1 - 5*x))^3.
E.g.f.: exp(x)*(exp(2*x) - 1)^2*x^2/32.
(End)
EXAMPLE
a(5)=30+15=45: the first summand corresponds to the case when one of the paths has three nodes (5*4*3/2=30 variants; division by 2 is due to directional independence) and the second to the case when both paths have two nodes (5!/(2!2!2!)=15 variants).
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Feb 18 2023
STATUS
approved