A360715 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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