[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.
More information about the SeqFan
mailing list