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

Andrew Howroyd, Table of n, a(n) for n = 1..500

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) + 6*3^(n-2) + 9).

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

From Andrew Howroyd, Nov 23 2025: (Start)

Binomial transform of A359405.

G.f.: x^2*(1 - 21*x + 183*x^2 - 850*x^3 + 2241*x^4 - 3213*x^5 + 1947*x^6)/((1 - x)*(1 - 3*x)*(1 - 5*x))^3. (End)

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.

Prog

(PARI) a(n) = n*(n-1)*2^(-5)*(5^(n-2) + 6*3^(n-2) + 9); \\ Andrew Howroyd, Nov 23 2025

Crossrefs

Column k=2 of A390897.

If there is only one path, we get A360715. If one-node paths are not allowed, we get A360716. If all points need to be used we get A359405.

Sequence in context: A006630 A367850 A180035 * A379139 A286187 A260774

Adjacent sequences: A360714 A360715 A360716 * A360718 A360719 A360720

Keyword

nonn,easy

Author

Ivaylo Kortezov, Feb 18 2023

Status

approved