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

[Simon Plouffe]

Hello everyone,

 the formula was found using gfun , in addition,
when one formula appears to be good, I usually
used factor () to see if a simplification could occur.
This reinforce the candidate as being potentially the
good one.

Gfun was created by me and François Bergeron in 1991,
at the time I was using 'ratpoly' from Maple , a pretty
good routine that uses 'padé approximants' . Now all
this is include in the standard GFUN package in maple
, it is also part of mathematica as well now.

For this, (in gfun), there is the 'listtoratpoly' which
forces maple to find a rational polynomial , it is
quite robust. If the size of the expression is too big
then it returns 'FAIL'.
The amount of effort of the listtoratpoly can be adjusted
by changing the default order of the expression,
See GFUN in the maple help.
Use this with caution because if forced to find it anyway,
it could hang the program.

Now about the combinatorial interpretation of  A005822 :
I know it counts some type of trees, that's about it.

Best regards,
 Simon Plouffe







Le sam. 25 janv. 2020 à 08:03, Neil Sloane <njasloane at gmail.com> a écrit :

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