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

Neil Sloane njasloane at gmail.com
Sat Jan 25 08:03:34 CET 2020

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

```