login
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.
5
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
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
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
KEYWORD
nonn,nice
AUTHOR
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