%I #22 Mar 04 2023 20:36:20

%S 0,0,0,3,45,435,3465,24794,165942,1061730,6578550,39796053,236309931,

%T 1382504669,7989938775,45704622660,259155482652,1458298435572,

%U 8151155034300,45290328792695,250308998693145,1376766613411959,7539656755416885,41126122248463038,223513887538508850,1210707873300202550,6537847299012919890

%N 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.

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

%H Ivaylo Kortezov, <a href="http://www.wfnmc.org/journal.html">Sets of Paths between Vertices of a Polygon</a>, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (27,-312,2016,-7986,19998,-31472,29880,-15525,3375).

%F a(n) = n*(n-1)*2^(-5)*(5^(n-2) - 2*3^(n-2) + 1).

%F From _Andrew Howroyd_, Feb 19 2023: (Start)

%F Binomial transform of A332426.

%F 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.

%F 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.

%F E.g.f.: exp(x)*(exp(2*x) - 1)^2*x^2/32.

%F (End)

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

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

%K nonn,easy

%O 1,4

%A _Ivaylo Kortezov_, Feb 18 2023