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

[Brendan McKay]

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/