login
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

%I #43 May 14 2022 04:57:39

%S 1,1,1,3,5,17,28,105,161,670,1001,2869,6188,26565,14502,167898,245157,

%T 445507,1562275,6055315,2571120,44247137,64512240,65610820,362592230,

%U 1850988412,591652989,11453679146,17620076360,1511122441,114955808528,511647729284,67876359922,3347789809236,1882352047787,1404030562068,32308782859535

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

%C 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]

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a030/A030077.java">Java program</a> (github)

%H Brendan D. McKay and Tim Peters, <a href="https://arxiv.org/abs/2205.06004">Paths through equally spaced points on a circle</a>, arXiv:2205.06004 [math.CO], 2022.

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

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

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

%Y See A352568 for the multisets of line lengths.

%K nonn,nice

%O 1,4

%A _Daniel Lurie Gittelson_, Dec 11 1999

%E a(13) - a(16) from _T. D. Noe_, Jan 09 2007

%E Removed unnecessary mention of dihedral group from definition. - _N. J. A. Sloane_, Apr 02 2022

%E 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

%E a(17) to a(37) from _Brendan McKay_, May 14 2022