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

Author

Ivaylo Kortezov, Feb 18 2023

Keywords

• nonn
• easy

Examples

			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.
		

Links

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

Crossrefs

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

Formula

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