[seqfan] Re: Spanning trees in the cube of a cycle (A005288)

Brendan McKay Brendan.McKay at anu.edu.au
Sat Jan 25 09:42:49 CET 2020


The Kleitman-Golden paper was a prior publication of exactly the
same result as appeared in the paper of Baron et al cited at A005822.

Brendan.

https://www.fq.math.ca/Scanned/23-3/baron.pdf

On 25/1/20 7:37 pm, Neil Sloane wrote:
> A friend just sent me a copy of the Kleitman-Golden paper.
>
> It doesn't solve Brendan's problem, but it has several other related
> sequences.
>
> One thing that puzzles me about the Baron et al 1985 Fib Quarterly paper
> that is the sole reference for A005822
> is that although it has many sequences in it, there is no other reference
> to this paper in either the EIS nor the OEIS .
> And there is no copy of the paper in the binder with the source
> material for sequences A5000-A5999.
> I admit I am the author-of-record for A005822, but this evidence suggests
> that it may have
> arrived in my office in a brown envelope with no return address...
>
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Sat, Jan 25, 2020 at 2:24 AM Neil Sloane <njasloane at gmail.com> wrote:
>
>> It is possible that the article
>>
>> D. J. Kleitman and B. Golden. "Counting Trees in a Certain Class of
>> Graphs." Amer. Math. Montlhy (1975), pp. 40-44. Vol 82, Number 1,
>>
>> may be relevant, but my Rutgers library login has suddenly  stopped
>> working and it 2am here .
>> Could someone get me a copy?
>>
>>
>> Best regards
>> Neil
>>
>> Neil J. A. Sloane, President, OEIS Foundation.
>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>> Phone: 732 828 6098; home page: http://NeilSloane.com
>> Email: njasloane at gmail.com
>>
>>
>>
>> On Sat, Jan 25, 2020 at 2:03 AM Neil Sloane <njasloane at gmail.com> wrote:
>>
>>> 1.  I will ask Simon Plouffe if he can remember anything about this
>>>
>>> 2.  I checked my old files, but did not find anything on an initial search
>>>
>>> 3.  If all else fails, I suggest we change the definition of A005822 to
>>> the generating function
>>> (1-x^2)*(x^4+x^3-x^2+x+1) / (x^8-4*x^6-x^4-4*x^2+1)
>>> and then Brendan you could submit your version that matches the words of
>>> the present definition as a new sequence.
>>>
>>> But let's wait to hear from Simon.
>>>
>>> Simon, Can you throw any light on A005822 (aka M1243)?
>>>
>>>
>>>
>>> Best regards
>>> Neil
>>>
>>> Neil J. A. Sloane, President, OEIS Foundation.
>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>>> Phone: 732 828 6098; home page: http://NeilSloane.com
>>> Email: njasloane at gmail.com
>>>
>>>
>>>
>>> On Fri, Jan 24, 2020 at 11:58 PM Brendan McKay <Brendan.McKay at anu.edu.au>
>>> wrote:
>>>
>>>> Yes, sorry, A005822.   Edited below. Brendan.
>>>>
>>>> On 25/1/20 1:26 pm, Sean A. Irvine wrote:
>>>>> You mean A005822 ...
>>>>>
>>>>> On Sat, 25 Jan 2020 at 14:31, Brendan McKay <Brendan.McKay at anu.edu.au>
>>>>> wrote:
>>>>>
>>>>>> It has been noticed on Mathoverflow that something is amiss with
>>>> A005288
>>>>>> "Number of spanning trees in third power of cycle".
>>>>>>
>>>>>> A5822(n) = 1, 1, 2, 4, 11, 16, 49, 72, 214, 319, 947, 1408, 4187,
>>>>>>              6223, 18502, 27504
>>>>>> offset: 1,3
>>>>>>
>>>>>> The simplest proof that there's a problem is that there is no graph on
>>>>>> 3 vertices with 2 spanning trees.
>>>>>>
>>>>>> I take "third power of cycle" to mean a graph whose edges join
>>>> vertices
>>>>>> arranged
>>>>>> in a cycle if they are at most 3 apart.  Up to 7 vertices it is a
>>>> complete
>>>>>> graph,
>>>>>> so the number of spanning trees is n^(n-2).  Starting at 7 vertices
>>>> it is a
>>>>>> regular graph of degree 6.
>>>>>>
>>>>>> By direct computation using the matrix tree theorem, I get actual
>>>> values
>>>>>> T(n) = 1, 1, 3, 16, 125, 1296, 16807, 82944, 412164, 2035220, 9864899,
>>>>>>        47579136, 227902597, 1084320412, 5134860060, 24207040512,
>>>>>>        113664879137, 531895993344
>>>>>>
>>>>>> I'm sure there is some relationship between A5288(n) and T(n) since
>>>>>> for n >= 7 and as far as I computed T(n) is a multiple of A5288(n).
>>>> Here
>>>>>> is the ratio T(n)/A5822(n) starting at n=7:  1152, 1926, 6380, 10417,
>>>>>> 33792,
>>>>>> 54431, 174244, 277530, 880128, 1390073, 4375872
>>>>>>
>>>>>> I conjecture  that T(n) = f(n)*A5822(n) for some f(n) that has been
>>>> lost,
>>>>>> and that this relation is only intended to hold for n>=7, or maybe
>>>> n>=8.
>>>>>> The cited works of Plouffe probably contain the explanation, but my
>>>>>> French is not up to it.
>>>>>>
>>>>>> Brendan.
>>>>>>
>>>>>> --
>>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>>
>>>>> --
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list