A030077 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A030077

Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct path lengths.

1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 2869, 6188, 26565, 14502, 167898, 245157, 445507, 1562275, 6055315, 2571120, 44247137, 64512240, 65610820, 362592230, 1850988412, 591652989, 11453679146, 17620076360, 1511122441, 114955808528, 511647729284, 67876359922, 3347789809236, 1882352047787, 1404030562068, 32308782859535

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

OFFSET

1,4

COMMENTS

For n points on a circle, there are floor(n/2) distinct line segment lengths. Hence an upper bound for a(n) is the number of compositions of n-1 into floor(n/2) nonnegative parts, which is A099578(n-2). Conjecture: the upper bound is attained if n is prime. There are A052558(n-2) paths to be considered. - T. D. Noe, Jan 09 2007 [Edited by Petros Hadjicostas, Jul 19 2018]

LINKS

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

Sean A. Irvine, Java program (github)

Brendan D. McKay and Tim Peters, Paths through equally spaced points on a circle, arXiv:2205.06004 [math.CO], 2022.

EXAMPLE

For n=4 the 3 lengths are: 3 boundary edges (length 3), edge-diagonal-edge (2 + sqrt(2)) and diagonal-edge-diagonal (1 + 2*sqrt(2)).

For n=5, the 4 edges of the path may include 0,...,4 diagonals, so a(5)=5.

CROSSREFS

Cf. A007874 (similar, but with n line segments), A052558, A099578.

See A352568 for the multisets of line lengths.

Sequence in context: A032619 A193066 A193070 * A352568 A058580 A161682

Adjacent sequences: A030074 A030075 A030076 * A030078 A030079 A030080

KEYWORD

nonn,nice

AUTHOR

Daniel Lurie Gittelson, Dec 11 1999

EXTENSIONS

a(13) - a(16) from T. D. Noe, Jan 09 2007

Removed unnecessary mention of dihedral group from definition. - N. J. A. Sloane, Apr 02 2022

The terms a(1) to a(15) have been verified by Sean A. Irvine and a(1) to a(16) by Brendan McKay. - N. J. A. Sloane, Apr 02 2022

a(17) to a(37) from Brendan McKay, May 14 2022

STATUS

approved