[seqfan] Re: Fwd: Worry about old sequence, A030077, paths in K_n, and new sequence A352568
Brendan McKay
Brendan.McKay at anu.edu.au
Sun Apr 3 11:09:13 CEST 2022
Thanks to a tip from Darryn Bryant, I have found that there is
substantial literature
related to A352568, that is
"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 [not path, Neil]
lengths".
The question is: Which multisets of segment lengths can be realised?
Baratti conjectured that all multisets can be realised if n is prime.
This is proved
up to n=23 but remains open in general.
Baratti, Horak and Rosa conjectured a complete answer to the the
question and many
special cases have been proved. Searching for these names gives many
hits, for
example:
https://doi.org/10.1016/j.disc.2021.112486
https://arxiv.org/pdf/1311.2785.pdf
https://www.combinatorics.org/ojs/index.php/eljc/article/download/109/pdf
https://www.researchgate.net/profile/Marco-Pellegrini-15/publication/337969707_Further_progress_on_the_Buratti-Horak-Rosa_conjecture/links/5dfb143492851c836488482a/Further-progress-on-the-Buratti-Horak-Rosa-conjecture.pdf
https://doi.org/10.1016/j.disc.2013.11.017
https://arxiv.org/abs/2202.07733
http://bica.the-ica.org/Volumes/94/Reprints/BICA2021-21-Reprint.pdf
I stopped there but there are plenty more.
Cheers, Brendan.
On 3/4/2022 2:09 pm, Neil Sloane wrote:
> I created A352568 for the number of multisets version. Feel free to
> edit it.
>
> Brendan, would you be willing to add your program to A030077 as a .txt
> file? As Antti just pointed out, we have had a lot of problems over
> the years because people did not post their programs. Antti says, and
> I agree, for the initial computation of a sequence, beauty is
> irrelevant. We just want to know how the numbers were computed. We
> don't care much if the program is ugly. Chances are no one will run
> it, but we do need to have it on record just in case.
>
> This is the same situation as with the first proof of a theorem. If
> the proof is elegant, so much the better. But all that really matters
> is that it must be correct.
>
> Another thing about this sequence: Could you and Robert Gerbicz put
> together some comments for the record, along the lines of the postings
> you both recently made? This could be another .txt file.
>
>
> Best regards
> Neil
>
> Neil J. A. Sloane, Chairman, OEIS Foundation.
> Also Visiting Scientist, Math. Dept., Rutgers University,
> Email: njasloane at gmail.com
>
>
>
> On Sat, Apr 2, 2022 at 11:04 PM Brendan McKay via SeqFan
> <seqfan at list.seqfan.eu> wrote:
>
> Another point on this. Consider three sequences:
>
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
> 16 1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 2869, 6188, 26565,
> 14502,
> 167898 1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 4129, 6188, 26565,
> 38591, 167898 1, 1, 4, 5, 21, 28, 120, 165, 715, 1001, 4368, 6188,
> 27132, 38760, 170544
>
> In order:
> A030077(n) distinct lengths, distinct multisets, A099578(n-2)
> binomial
> coeff.
>
> The comment in A030077 (Noe, edited by Hadjicostas) says
> "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). It appears that the
> upper
> bound is attained for prime n."
>
> I don't think "it appears" counts for much and I propose this last
> sentence
> be removed or restated more clearly as a conjecture.
>
> Robert Gerbicz showed us recently that distinct multisets have
> distinct
> lengths in the prime case, but it remains to be shown that all
> multisets
> can be achieved in the prime case. If n is not prime and k is a
> proper
> divisor of n, then the multisets with every element a multiple of
> k are
> not achieved. (First case: 3 diagonals for n=4.)
>
> Brendan.
>
> On 3/4/2022 11:57 am, Brendan McKay via SeqFan wrote:
> > It took 4.7 hours to do n=16. There are 167898 distinct
> multisets of
> > edge lengths, and no two of them are closer than 10^{-7} in total
> > length. So the value in the existing A052558 entry is correct.
> >
> > Thus, I believe all the values in the entry are correct. The
> reason the
> > graph looks dubious is that only for some values can distinct
> multisets
> > have the same total. For n <= 16, this happens only for 12 and 15.
> >
> > The number of distinct multisets of edge lengths up to n=16 is
> > 1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 4129, 6188, 26565,
> 38591,
> > 167898,
> > which is not in OEIS.
> >
> > Now I will run n=17.
> >
> > Brendan.
> >
> > On 3/4/2022 12:51 am, Brendan McKay via SeqFan wrote:
> >> Dear Seqfans,
> >>
> >> The values are correct up to 15 points (800 seconds cpu).
> >> n=16 will run overnight, and I will do 17 too but it might take
> a week.
> >> My method is exact, with no guesswork about approximate arithmetic.
> >>
> >> I trace all paths (limited by fixed starting point and
> direction to
> >> go first).
> >> As I do that, I collect which multisets of edge lengths occur, the
> >> number
> >> of which is not in OEIS but should be.
> >>
> >> Then I sort the multisets by their length calculated with 19-digit
> >> arithmetic.
> >> Lengths whose approximation differs by 10^{-7} (using the unit
> circle)
> >> or more can't possibly be equal. (That's a rigorous fact.)
> >>
> >> That leaves some collections of multisets whose approximations
> differ by
> >> less than 10^{-17}. So far no differences between 10^{-17} and
> 10^{-7}
> >> have appeared. For all those probably-equal lengths, Maple's
> >> simplify( )
> >> function manages to show they are exactly equal.
> >>
> >> I figured out where the dihedral group comes in. It is
> relevant to
> >> the comment
> >> "there are A052558(n-2) paths to be considered" since A052558(n-2)
> >> counts
> >> equivalence classes of directed hamiltonian paths under the
> dihedral
> >> group.
> >> It isn't quite correct that only that many paths need considering,
> >> since almost
> >> another factor of 2 could be achieved by considering the
> reverse of
> >> the path
> >> (but I'm not using that).
> >>
> >> For some reason I only see a fraction of seqfan postings, so
> please
> >> CC me
> >> on anything you want me to see.
> >>
> >> Cheers, Brendan.
> >>
> >>
> >> --
> >> Seqfan Mailing list -
> >>
> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cadae57b1ee3246da9aec08da151549f1%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845478737341929%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=tGFoBHtZmHcmUUjV3zR4%2BJWE7Z9C51FESQ21BomTISU%3D&reserved=0
> <https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7CBrendan.McKay%40anu.edu.au%7C2617183f7f3d48f4066608da1527cb3f%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845558051663948%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=A09fGksYsKqqn9yHzZPTypyH8OnYZC3n0A7lyW4mOoQ%3D&reserved=0>
> >
> > --
> > Seqfan Mailing list -
> >
> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7Cadae57b1ee3246da9aec08da151549f1%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845478737341929%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=tGFoBHtZmHcmUUjV3zR4%2BJWE7Z9C51FESQ21BomTISU%3D&reserved=0
> <https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7CBrendan.McKay%40anu.edu.au%7C2617183f7f3d48f4066608da1527cb3f%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845558051663948%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=A09fGksYsKqqn9yHzZPTypyH8OnYZC3n0A7lyW4mOoQ%3D&reserved=0>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
> <https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7CBrendan.McKay%40anu.edu.au%7C2617183f7f3d48f4066608da1527cb3f%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845558051663948%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=A09fGksYsKqqn9yHzZPTypyH8OnYZC3n0A7lyW4mOoQ%3D&reserved=0>
>
More information about the SeqFan
mailing list