%I #45 May 02 2022 20:46:40
%S 1,4,12,128,605,3072,16807,82944,412164,2035220,9864899,47579136,
%T 227902597,1084320412,5134860060,24207040512,113664879137,
%U 531895993344,2481300851179,11543181696640,53565699079956,248005494380204,1145875775104967,5284358088818688
%N Number of spanning trees in the multigraph cube of an n-cycle.
%C The multigraph cube of an n-cycle has n nodes V1, V2, ... Vn, with one edge Vi to Vj for each pair (i,j) such that j = i+1, i+2 or i+3 modulo n. It is a multigraph when n <= 6 because this produces instances of multiple edges between the same two vertices, and it also produces loops if n <= 3.
%C Baron et al. (1985) describes the corresponding sequence A169630 for the multigraph square of a cycle.
%C I conjecture that a(n) = gcd(n,2) * n * (A005822(n))^2. [This is correct - see the Formula section. - _N. J. A. Sloane_, Feb 06 2020)
%C Terms a(7) to a(18) calculated by _Brendan McKay_, and terms a(1) to a(6) by _David J. Seal_, in both cases using Kirchhoff's matrix tree theorem.
%H Alois P. Heinz, <a href="/A331905/b331905.txt">Table of n, a(n) for n = 1..1546</a>
%H G. Baron et al., <a href="http://www.fq.math.ca/Scanned/23-3/baron.pdf">The number of spanning trees in the square of a cycle</a>, Fib. Quart., 23 (1985), 258-264.
%H Yoshiaki Doi et al., <a href="/A331905/a331905_1.pdf">A note on spanning trees</a>
%H Min Li, Zhibing Chen, Xiaoqing Ruan, and Xuerong Yong, <a href="https://doi.org/10.1016/j.disc.2015.04.025">The formulas for the number of spanning trees in circulant graphs</a>, Disc. Math. 338 (11) (2015) 1883-1906, Lemma 1.
%F The following formulas were provided by Tsuyoshi Miezaki on Feb 05 2020 (see Doi et al. link). Let z1=(-3+sqrt(-7))/4, z2=(-3-sqrt(-7))/4; T(n,z) = cos(n*arccos(z)). Then a(n) = (2*n/7)*(T(n,z1)-1)*(T(n,z2)-1). Furthermore a(n) = 2*n*A005822(n)^2 if n is even, or n*A005822(n)^2 if n is odd. - _N. J. A. Sloane_, Feb 06 2020
%e The multigraph cube of a 4-cycle has four vertices, with two edges between each pair of distinct vertices - i.e., it is a doubled-edge cover of the complete graph on 4 vertices. The complete graph on 4 vertices has 4^2 = 16 spanning trees, and each of those spanning trees corresponds to 8 spanning trees of the multigraph tree because there are independent choices of 2 multigraph edges to be made for each of the three edges in the graph's spanning tree. So a(4) = 16 * 8 = 128.
%p a:= n-> ((<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|4|1|4>>^iquo(n, 2, 'd').
%p <[<0, 1, 4, 16>, <1, 2, 11, 49>][d+1]>)[1, 1])^2*n*(2-irem(n, 2)):
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Feb 06 2020
%Y Cf. A005822, A169630 (corresponding sequence for the multigraph square of an n-cycle).
%K nonn
%O 1,2
%A _David J. Seal_, Jan 31 2020
%E More terms from _Alois P. Heinz_, Feb 06 2020