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.

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

Table of n, a(n) for n=1..27.

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

Adjacent sequences: A360713 A360714 A360715 * A360717 A360718 A360719

Keyword

nonn,easy

Author

Ivaylo Kortezov, Feb 18 2023

Status

approved