A360717 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 allowed.

0, 1, 6, 33, 185, 1050, 6027, 35014, 205326, 1209375, 7119860, 41744703, 243218703, 1406685280, 8073640785, 45991600860, 260131208396, 1461591509805, 8162196518322, 45327133739245, 250431036147285, 1377169337010390, 7540979990097191, 41130452834689218, 223528009015333050, 1210753768099880875, 6537995998163877312

Offset: 1

Author

Ivaylo Kortezov, Feb 18 2023

Keywords

• nonn

Comments

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

Examples

			a(4) = A359405(4) + 4*A359405(3) + 4*3/2 = 15 + 12 + 6 = 33 with the three summands corresponding to the cases of 4, 3 and 2 used points.
		

Links

• Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.

Crossrefs

If there is only one path, we get A360715. If one-node paths are not allowed, we get A360716.

Formula

a(n) = n*(n-1)*2^(-5)*(5^(n-2) + 6*3^(n-2) + 9).

E.g.f.: exp(x)*((x*exp(2*x) + 3*x)/4)^2/2. - Andrew Howroyd, Feb 19 2023