cp's OEIS Frontend

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

%I A352568 #52 Jun 20 2025 10:46:48
%S A352568 1,1,1,3,5,17,28,105,161,670,1001,4129,6188,26565,38591,167898,245157,
%T A352568 1072730,1562275,6871780,10011302,44247137,64512240,285599304,
%U A352568 417219530,1850988412,2707392498,12026818454,17620076360,78356395953,114955808528,511647729284,751614362180,3347789809236,4923688862065,21944254861680,32308782859535
%N A352568 Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct multisets of segment lengths.
%C A352568 This sequence is different from A030077 because there we only look at how many different total path lengths occur, whereas here we look at which individual segment lengths occur in the path. The latter count may be larger, because it can happen that two paths whose compositions are distinct can have the same total length. For n <= 16 this happens just when n is 12 and 15.
%C A352568 Say the type of a segment is its position in the increasing list of floor(n/2) possible segment lengths. The Buratti-Horak-Rosa conjecture is that the following condition is necessary and sufficient for a multiset to be realizable as a path: for each divisor d of n, the number of segments of type divisible by d is at most n-d. The sequence confirms the conjecture up to n=37. - _Brendan McKay_, May 14 2022
%C A352568 If the Buratti-Horak-Rosa conjecture is true, the values of a(38)-a(50) are 144079707346575, 212327989773900, 947309492837400, 1397281501935165, 6236646703759395, 9206478467454345, 41107996877935680, 60727722660586800, 271250494550621040, 400978991944396320, 1791608261879217600, 2650087220696342700, 11844267374132633700. - _Brendan McKay_, Jun 14 2022
%D A352568 Brendan McKay, Posting to Sequence Fans Mailing List, April 02 2022.
%H A352568 Samuel C. Gutekunst, <a href="https://arxiv.org/abs/2506.10758">Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds</a>, arXiv:2506.10758 [cs.DM], 2025. See pp. 2-3, 6, 17-18.
%H A352568 P. Horak and A. Rosa, <a href="https://doi.org/10.37236/109">On a problem of Marco Burrati</a>, Electronic J. Combinatorics, 16 (2009) R20.
%H A352568 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.
%H A352568 A. Pasotti and M. A. Pellegrini, <a href="https://doi.org/10.37236/3879">On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs</a>, Electronic J. Combinatorics, 21 (2014) P2.30.
%e A352568 For n = 4 there are two possible edge lengths, the side and the diagonal of the square. For a path with three line segments, we can have 3 sides, 2 sides and one diagonal, or 2 diagonals and one side. So a(4) = 3.
%Y A352568 Cf. A030077.
%K A352568 nonn
%O A352568 1,4
%A A352568 _N. J. A. Sloane_, Apr 02 2022
%E A352568 Definition adjusted by _Brendan McKay_, Apr 03 2022
%E A352568 a(17) to a(37) from _Brendan McKay_, May 14 2022