# [seqfan] Notes on A030077 and A352568 (lengths of paths through equally spaced points on a circle)

Brendan McKay Brendan.McKay at anu.edu.au
Mon Apr 4 09:09:24 CEST 2022

We have n points equally spaced on a circle.

Abbreviations:
n/2  means floor(n/2)
A multiset means a multiset of n-1 choices from {1,2,...,n/2}.
A number k in {1,2,...,n/2} means the k-th shortest chord length.

The number of multisets is binomial(n-2+n/2,n-1) = A099578(n-2).

Call a multiset "realizable" if there is a path through the n points
whose chord lengths give the multiset.
The number of realizable multisets is A352568(n).

Call a multiset "admissible" if it satisfies this property:
for any divisor d of n, the number of multiples of d in the multiset
is at most n-d.

Horak and Rosa proved that  realizable => admissible.

The Buratti-Horak-Rosa (BHR) conjecture is that admissible => realizable
as well.

The BHR conjecture has been proved for n <= 19, n = 23, and for many
special multisets.

Accordingly, A352568 can be extended to n=19 without enumerating paths,
since the number of admissible multisets is vastly smaller than the
number of paths.  I have these counts and will add them.

Similarly, A030077 (number of different path lengths) can be extended to
n=19 by comparing the path lengths of all the admissible multisets. I
have these too, it only takes a few seconds with exact arithmetic.

Up to n=25, there are distinct admissible multisets giving the same
length in the cases 12, 15, 18, 20, 21, 24 and 25.  Not 16 or 22.  Is
there a plausible pattern?

References:

https://doi.org/10.37236/109
https://doi.org/10.37236/3879

Brendan.