A175243 Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

1, 2, 1, 3, 12, 3, 4, 75, 294, 16, 5, 384, 11664, 16384, 125, 6, 1805, 367500, 5647152, 1640250, 1296, 7, 8100, 10609215, 1528823808, 6291456000, 259200000, 16807, 8, 35287, 292626432, 380008339280, 18911429680500, 13556617751088, 59549251454

Offset

1,2

Links

Table of n, a(n) for n=1..35.

F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs Combinat. 2 (1986) 191-200.

Index entries for sequences related to trees

Formula

R_n(m) = n*2^(m-1)* (T(n,1+m/2)-1)^(m-1)/m, where T(n,x) are Chebyshev polynomials, A008310.

Each column of the array is a linear divisibility sequence. Conjecturally, the k-th column satisfies a linear recurrence of order 4*k - 2. - Peter Bala, May 04 2014

Example

The array starts in row n=1 as:
  1,    1,        3,         16,        125
  2,   12,      294,      16384,    1640250
  3,   75,    11664,    5647152, 6291456000
  4,  384,   367500, 1528823808,
  5, 1805, 10609215,

Maple

A175243 := proc(n, m) n*2^(m-1)/m*( orthopoly[T](n, 1+m/2)-1)^(m-1) ; end proc:
for d from 2 to 10 do for m from 1 to d-1 do n := d-m ; printf("%d, ", A175243(n, m)) ; end do: end do:

Mathematica

r[n_, m_] := n*2^(m-1)*(ChebyshevT[n, 1+m/2]-1)^(m-1)/m; Table[r[n-m, m], {n, 2, 9}, {m, 1, n-1}] // Flatten (* Jean-François Alcover, Jan 10 2014 *)

Crossrefs

Cf. A006235 (column 2), A000272, A212798 (column 3).

Sequence in context: A122050 A081323 A173958 * A168217 A329025 A317548

Adjacent sequences: A175240 A175241 A175242 * A175244 A175245 A175246

Keyword

easy,nonn,tabl

Author

R. J. Mathar, Mar 13 2010

Status

approved