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,3

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.

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

Example

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.

Crossrefs

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

Sequence in context: A006630 A367850 A180035 * A379139 A286187 A260774

Adjacent sequences: A360714 A360715 A360716 * A360718 A360719 A360720

Keyword

nonn

Author

Ivaylo Kortezov, Feb 18 2023

Status

approved