|
%I #64 Jan 14 2021 17:38:10
%S 1,2,1,3,12,1,4,75,70,1,5,384,1728,408,1,6,1805,31500,39675,2378,1,7,
%T 8100,508805,2558976,910803,13860,1,8,35287,7741440,140503005,
%U 207746836,20908800,80782,1,9,150528,113742727,7138643400,38720000000,16864848000,479991603,470832,1
%N Number A(n,k) of spanning trees in C_k X P_n; square array A(n,k), n>=1, k>=1, read by antidiagonals.
%C Every row and every column of the array is a divisibility sequence, i.e., the terms satisfy the property that if n divides m then a(n) divides a(m) provided a(n) > 0. This follows from the representation of the elements of the array as a resultant. - _Peter Bala_, May 01 2014
%H Alois P. Heinz, <a href="/A173958/b173958.txt">Antidiagonals n = 1..45, flattened</a>
%H Germain Kreweras, <a href="http://dx.doi.org/10.1016/0095-8956(78)90021-7">Complexité et circuits Eulériens dans les sommes tensorielles de graphes</a>, J. Combin. Theory, B 24 (1978), 202-212. See p. 210. - From _N. J. A. Sloane_, May 27 2012
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">Kirchhoff's theorem</a>
%F A(n,k) = m*Prod(Prod( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1) [Kreweras]. - From _N. J. A. Sloane_, May 27 2012
%F Let T(n,x) and U(n,x) denote the Chebyshev polynomials of the first and second kind respectively. Let R(n,x) = 2*( T(n,(x + 2)/2) - 1 )/x (the row polynomials of A156308). Then the (n,k)-th element of the array = resultant (R(k,x), U(n-1,(2 - x)/2). - _Peter Bala_, May 01 2014
%e Square array A(n,k) begins:
%e 1, 2, 3, 4, 5, ...
%e 1, 12, 75, 384, 1805, ...
%e 1, 70, 1728, 31500, 508805, ...
%e 1, 408, 39675, 2558976, 140503005, ...
%e 1, 2378, 910803, 207746836, 38720000000, ...
%p with(LinearAlgebra):
%p A:= proc(n, m) local M, i, j;
%p if m=1 then 1 else
%p M:= Matrix(n*m, shape=symmetric);
%p for i to n do
%p for j to m-1 do M[m*(i-1)+j, m*(i-1)+j+1]:=-1 od;
%p M[m*(i-1)+1, m*i]:= M[m*(i-1)+1, m*i]-1
%p od;
%p for i to n-1 do
%p for j to m do M[m*(i-1)+j, m*i+j]:=-1 od
%p od;
%p for i to n*m do
%p M[i,i]:= -add(M[i,j], j=1..n*m)
%p od;
%p Determinant(DeleteColumn(DeleteRow(M, 1), 1))
%p fi
%p end:
%p seq(seq(A(n, 1+d-n), n=1..d), d=1..9);
%p # Crude Maple program from _N. J. A. Sloane_, May 27 2012:
%p Digits:=200;
%p T:=(m,n)->round(Re(evalf(simplify(expand(
%p m*mul(mul( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1))))));
%p # Alternative program using the resultant:
%p for n from 1 to 10 do seq(k*resultant(simplify((2*(ChebyshevT(k,(x + 2)/2) - 1))/x), simplify(ChebyshevU(n-1,1 - x/2)), x), k = 1 .. 10) end do; # _Peter Bala_, May 01 2014
%t t[m_, n_] := m*Product[Product[4*Sin[h*Pi/m]^2 + 4*Sin[k*Pi/(2*n)]^2, {h, 1, m-1}], {k, 1, n-1}]; Table[t[m, n-m+1] // Round, {n, 1, 9}, {m, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Dec 05 2013, after _N. J. A. Sloane_ *)
%Y Columns k=1-11 give: A000012, A001542, A003690, A003753, A003733, A158880, A158898, A210812, A174001, A210813, A174089.
%Y Rows n=1-2 give: A000027, A006235.
%Y Main diagonal gives A252767.
%Y Cf. A156308.
%K nonn,tabl
%O 1,2
%A _Alois P. Heinz_, Nov 26 2010
|
