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

Richard J. Mathar mathar at mpia-hd.mpg.de
Fri Jan 31 15:13:14 CET 2020

```njas> Date: Sat, 25 Jan 2020 03:37:18 -0500
njas> From: Neil Sloane <njasloane at gmail.com>
njas> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>, Simon
njas>         Plouffe <simon.plouffe at gmail.com>
njas> Subject: [seqfan] Re: Spanning trees in the cube of a cycle (A005288)
njas> ...
njas> One thing that puzzles me about the Baron et al 1985 Fib Quarterly paper
njas> that is the sole reference for A005822
njas> is that although it has many sequences in it, there is no other reference
njas> to this paper in either the EIS nor the OEIS .

In the paper
G. Baron, H. Prodinger, R. F. Tichy, <a href="https://www.fq.math.ca/23-3.html">The number of spanning trees in the square of a cycle</a>, Fib. Qart. (1985) 258:

- The sequence t(W_n)  is A004146 (see comment of Emeric there).

- The sequence n*F_n^2=t(C_n^2) is A169630

- The sequence n^2*F_n^2 = =n*t(C^2) = A045925(n)^2 = 1, 4, 36, 144, 625, 2304, 8281, 28224, 93636, 302500 (n>=0)
is not in the OEIS (strange but true ?).
G.f.: -x*(x-1)*(x^6-x^5+17*x^4-12*x^3+17*x^2-x+1) / ( (1+x)^3*(x^2-3*x+1)^3 ). - ~~~~
<a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (6,-6,-19,24,24,-19,-6,6,-1).

- The sequence of the V_k-Determinants is 4,15,50,125,384,1183, 3528, 10404, 30250, 87131, 248832, 705757, 1989806, 5581500, 15586704 (n>=1)
is not in the OEIS, but essentially a duplicate of A169630.

- The sequence of the A_k-Determintants is 4, 15, 50, 160, 494, 1491, 4420, 12925, 37380, 107136, 304764, 861445, 2421700, 6775755, 18879734, k>=1
is apparently not in the OEIS

A := proc(k)
M := Matrix(k,k) ;
for r from 1 to k do
for c from 1 to k do
if r = c then
M[r,c] := 4 ;
elif abs(r-c) <= 2 then
M[r,c] := -1 ;
fi ;
end do:
end do:
LinearAlgebra[Determinant](M) ;
end proc:
seq(A(n),n=1..25) ;

G.f.: -x*(-4+5*x+5*x^2-5*x^3+x^4) / ( (1+x)*(x^2-3*x+1)^2 ). - ~~~~
<a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-5,-5,5,-1).
a(n) +a(n+1) = A001870(n+1).

- The sequence of B_k-Determinants is -1, -5, -20, -70, -200, -624, -1937, -5817, -17238, -50325, -145426, -416448, -1183873, n>=1

Ank := proc(r,c,k)
if r = c then
4 ;
elif abs(r-c) <= 2 then
-1 ;
elif r = 1 and c = k then
-1 ;
elif r = k and c = 1 then
-1 ;
else
0 ;
fi ;
end proc:

B := proc(k)
M := Matrix(k,k) ;
for r from 1 to k do
for c from 1 to k do
if r = 1 and c <= 2 then
M[r,c] := -1 ;
elif c = 1 and r <= 3 then
M[r,c] := -1 ;
elif r >=2 and c >=2 then
M[r,c] := Ank(r-1,c-1,k-1) ;
fi ;
end do:
end do:
LinearAlgebra[Determinant](M) ;
end proc:
seq(B(n),n=1..20) ;

G.f.: -x-5*x^2-20*x^3-70*x^4 +x^5*(-200+176*x+559*x^2-69*x^3-210*x^4+57*x^5) / ( (1+x)^2*(x^2-3*x+1)^2 ).
<a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,0,-10,0,4,-1).
Can obviously be formulated in terms of A001906 and A001871.

- the sequence of C_k-Determinants is -1, 5, -10, 30, -100, 288, -832, 2373, -6732, 18975, -53222, 148608, -413342, 1145703, -3165900, 8724093, -23980552..., k>=1

Ank := proc(r,c,k)
if r = c then
4 ;
elif abs(r-c) <= 2 then
-1 ;
elif r = 1 and c = k then
-1 ;
elif r = k and c = 1 then
-1 ;
else
0 ;
fi ;
end proc:

C := proc(k)
M := Matrix(k,k) ;
for r from 1 to k do
for c from 1 to k do
if r = 1 and c <= 2 then
M[r,c] := -1 ;
elif c = k and r >= k-1 then
M[r,c] := -1 ;
elif r >=2 and c <k then
M[r,c] := Ank(r-1,c,k-1) ;
fi ;
end do:
end do:
LinearAlgebra[Determinant](M) ;
end proc:
seq(C(n),n=1..27) ;

with similar trivial generating functions and recurrences.

I did not check that any of the linear superpositions fulfill the formulas in the Lemmata of the paper.
I will NOT submit any of these...

RJM

```