[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.

    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?




More information about the SeqFan mailing list