login
A360716
Number of unordered pairs of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.
3
0, 0, 0, 3, 45, 435, 3465, 24794, 165942, 1061730, 6578550, 39796053, 236309931, 1382504669, 7989938775, 45704622660, 259155482652, 1458298435572, 8151155034300, 45290328792695, 250308998693145, 1376766613411959, 7539656755416885, 41126122248463038, 223513887538508850, 1210707873300202550, 6537847299012919890
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
If there is only one path, we get A261064. If all n points need to be used, we get A332426.
Sequence in context: A117972 A061532 A309453 * A060242 A271236 A270064
KEYWORD
nonn,easy
AUTHOR
Ivaylo Kortezov, Feb 18 2023
STATUS
approved