A173958 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.

1, 2, 1, 3, 12, 1, 4, 75, 70, 1, 5, 384, 1728, 408, 1, 6, 1805, 31500, 39675, 2378, 1, 7, 8100, 508805, 2558976, 910803, 13860, 1, 8, 35287, 7741440, 140503005, 207746836, 20908800, 80782, 1, 9, 150528, 113742727, 7138643400, 38720000000, 16864848000, 479991603, 470832, 1

Offset

1,2

Comments

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

Links

Alois P. Heinz, Antidiagonals n = 1..60, flattened

Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210. - From N. J. A. Sloane, May 27 2012

Eric Weisstein's World of Mathematics, Cycle Graph

Eric Weisstein's World of Mathematics, Path Graph

Wikipedia, Kirchhoff's theorem

Formula

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

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 equals k times the resultant (R(k,x), U(n-1,(2 - x)/2)). - Peter Bala, May 01 2014 [Corrected by Pontus von Brömssen, Apr 08 2025]

Example

Square array A(n,k) begins:
  1,    2,      3,         4,           5,  ...
  1,   12,     75,       384,        1805,  ...
  1,   70,   1728,     31500,      508805,  ...
  1,  408,  39675,   2558976,   140503005,  ...
  1, 2378, 910803, 207746836, 38720000000,  ...

Maple

with(LinearAlgebra):
A:= proc(n, m) local M, i, j;
     if m=1 then 1 else
      M:= Matrix(n*m, shape=symmetric);
      for i to n do
        for j to m-1 do M[m*(i-1)+j, m*(i-1)+j+1]:=-1 od;
        M[m*(i-1)+1, m*i]:= M[m*(i-1)+1, m*i]-1
      od;
      for i to n-1 do
        for j to m do M[m*(i-1)+j, m*i+j]:=-1 od
      od;
      for i to n*m do
        M[i, i]:= -add(M[i, j], j=1..n*m)
      od;
      Determinant(DeleteColumn(DeleteRow(M, 1), 1))
     fi
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..9);
# Alternative:
Digits:=200;
T:=(m, n)->round(Re(evalf(simplify(expand(
m*mul(mul( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1)))))); # N. J. A. Sloane, May 27 2012
# Alternative: using the resultant
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

Mathematica

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 *)

Crossrefs

Columns k=1-11 give: A000012, A001542, A003690, A003753, A003733, A158880, A158898, A210812, A174001, A210813, A174089.

Rows n=1-2 give: A000027, A006235.

Main diagonal gives A252767.

Cf. A156308.

Sequence in context: A187111 A122050 A081323 * A372563 A175243 A168217

Adjacent sequences: A173955 A173956 A173957 * A173959 A173960 A173961

Keyword

nonn,tabl

Author

Alois P. Heinz, Nov 26 2010

Status

approved