[seqfan] Re: Spanning trees in the cube of a cycle (A005288)
David Seal
david.j.seal at gwynmop.com
Sun Feb 2 21:38:15 CET 2020
Chris Thompson has pointed the following paper out to me:
Min Li, Zhibing Chen, Xiaoqing Ruan, Xuerong Yong,
The formulas for the number of spanning trees in circulant graphs,
Discrete Mathematics, Volume 338, Issue 11, 2015, Pages 1883-1906,
https://doi.org/10.1016/j.disc.2015.04.025
Its Lemma 1 provides a formula for A331905 (the number of spanning trees of the multigraph third power of a cycle): it is 1/nth of the product from j = 1 to n-1 of term(j) = (6 - 2cosO(j/n) - 2cosO(2j/n) - 2cosO(3j/n)), where cosO(x) = cos(2*pi*x) is the cosine function 'squashed' to have period 1. So the values of cosO() that are subtracted are the real parts of nth roots of unity - which suggests a connection with cyclotomic polynomials that I've yet to investigate (it may be in the above paper, whose results I have used without yet having really absorbed the proofs).
Anyway, it's easily observed that term(j) = term(n-j) and that if n is even, term(n/2) = 6 - 2cosO(0.5) - 2cosO(1) - 2cosO(1.5) = 6 - (-2) - 2 - (-2) = 8, so:
* if n is odd, A331905(n) = (1/n) * square(product from j = 1 to (n-1)/2 of term(j))
* if n is even, A331905(n) = (8/n) * square(product from j = 1 to n/2-1 of term(j))
Calculating a few of the products in that formulation, I found that they were all coming out as integers. At this point, I thought of Brendan's original observation about the sequence seeming to always be a multiple of A005822 - was it perhaps always a multiple of A005822 squared? This was easy to check:
n A331905(n) A005822(n) A331905(n)/(A005822(n))^2
-------------------------------------------------------
1 1 1 1
2 4 1 4
3 12 2 3
4 128 4 8
5 605 11 5
6 3072 16 12
7 16807 49 7
8 82944 72 16
9 412164 214 9
10 2035220 319 20
11 9864899 947 11
12 47579136 1408 24
13 227902597 4187 13
14 1084320412 6223 28
15 5134860060 18502 15
16 24207040512 27504 32
17 113664879137 81769 17
18 531895993344 121552 36
The pattern seems pretty clear, so I conjecture that the connection between A005822 and A331905 is:
A331905(n) = n * (A005822(n))^2 if n is odd
2n * (A005822(n))^2 if n is even.
This is incidentally reminiscent of the result proved in the paper by Baron et al in the links from the sequences, that the corresponding sequence for the square of a cycle is n * (Fibonacci(n))^2, i.e. A169630.
David
> On 01 February 2020 at 01:21 David Seal <david.j.seal at gwynmop.com> wrote:
>
>
> Sorry I've been a bit slow to respond to Neil's request, but I have now submitted A331905. It's a rather 'bare bones' attempt, and I may well have missed important references, etc - but it's about all I can do at present.
>
> David
>
>
> > On 25 January 2020 at 16:50 Neil Sloane <njasloane at gmail.com> wrote:
> >
> >
> > I think David Seal is on the right track, when he says:
> >
> > > I observe that if one takes "third power of cycle" to mean the multigraph
> > whose edges join vertices arranged in a cycle if they are at most 3 apart,
> > with multiple edges sometimes appearing between vertices if the cycle has 6
> > or fewer vertices (following what the penultimate page of
> > http://www.fq.math.ca/Scanned/23-3/baron.pdf does for 4 or fewer vertices
> > in the square of a cycle), then the first six values of T(n) rise to 1, 4,
> > 12, 128, 605, 3072."
> >
> > and then the sequence would continue with the values that Brendan found.
> >
> > David, Could you please submit this sequence, and email me the A-number?
> > Then I will do some editing to A005822. ( will change its definition to
> > the generating function, and say that the connection with trees is unclear.
> >
> >
> > 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 9:55 AM David Seal <david.j.seal at gwynmop.com> wrote:
> >
> > > > On 25 January 2020 at 01:30 Brendan McKay <Brendan.McKay at anu.edu.au>
> > > wrote:
> > > > ...
> > > > 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.
> > >
> > > I observe that if one takes "third power of cycle" to mean the multigraph
> > > whose edges join vertices arranged in a cycle if they are at most 3 apart,
> > > with multiple edges sometimes appearing between vertices if the cycle has 6
> > > or fewer vertices (following what the penultimate page of
> > > http://www.fq.math.ca/Scanned/23-3/baron.pdf does for 4 or fewer vertices
> > > in the square of a cycle), then the first six values of T(n) rise to 1, 4,
> > > 12, 128, 605, 3072. That makes it always be a multiple f(n)*A005822(n) of
> > > A005822(n), with the first six values of f(n) being 1, 4, 6, 32, 55, 192.
> > >
> > > This tends to confirm that A005822 really is something to do with third
> > > powers of cycles, but I'm afraid I haven't managed to work out what!
> > >
> > > David
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list