# [seqfan] Re: Fwd: Worry about old sequence, A030077, paths in K_n

Brendan McKay Brendan.McKay at anu.edu.au
Sun Apr 3 05:04:02 CEST 2022

```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 -