A360715 Number of self-avoiding paths with nodes chosen among n given points on a circle; one-node paths are allowed.

1, 3, 9, 30, 105, 369, 1281, 4380, 14769, 49215, 162393, 531450, 1727193, 5580141, 17936145, 57395640, 182948577, 581130747, 1840247337, 5811307350, 18305618121, 57531942633, 180441092769, 564859072980, 1765184603025, 5507375961399, 17157594341241, 53379182394930, 165856745298489, 514727830236645

Offset

1,2

Links

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

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 (8,-22,24,-9).

Formula

a(n) = (n/4)*(3^(n-1) + 3).

From Andrew Howroyd, Nov 23 2025: (Start)

a(n) = n + Sum_{k=2..n} binomial(n,k)*A001792(k-2).

E.g.f.: exp(x)*(x*exp(2*x) + 3*x)/4.

G.f.: x*(1 - 5*x + 7*x^2)/((1 - x)*(1 - 3*x))^2. (End)

Example

a(4) = A001792(2) + 4*A001792(1) + 6 + 4 = 8 + 4*3 + 6 + 4 = 30 with the four summands corresponding to paths with 4, 3, 2 and 1 nodes, respectively.

Prog

(PARI) a(n) = (n/4)*(3^(n-1) + 3) \\ Andrew Howroyd, Nov 23 2025

Crossrefs

Column k=1 of A390897.

If one-node paths are not allowed, one gets A261064. Cf. A001792 if all n points need to be used.

Sequence in context: A145268 A148956 A339036 * A003409 A029651 A316371

Adjacent sequences: A360712 A360713 A360714 * A360716 A360717 A360718

Keyword

nonn,easy

Author

Ivaylo Kortezov, Feb 18 2023

Status

approved