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

[Neil Sloane]

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