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

[Sean A. Irvine]

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".
>
> A5288(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)/A5288(n) starting at n=7:  1152, 1926, 6380, 10417,
> 33792,
> 54431, 174244, 277530, 880128, 1390073, 4375872
>
> I conjecture  that T(n) = f(n)*A5288(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/
>