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

Author

Ivaylo Kortezov, Feb 18 2023

Keywords

• nonn
• easy

Comments

Although each path is self-avoiding, the different paths are allowed to intersect.

Examples

			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).
		

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).

Crossrefs

If there is only one path, we get A261064. If all n points need to be used, we get A332426.

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)