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

Table of n, a(n) for n=1..30.

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

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.

Crossrefs

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 * A029651 A003409 A316371

Adjacent sequences: A360712 A360713 A360714 * A360716 A360717 A360718

Keyword

nonn,easy

Author

Ivaylo Kortezov, Feb 18 2023

Status

approved