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

Author

R. J. Mathar, Mar 13 2010

Keywords

• easy
• nonn
• tabl

Examples

			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,
		

Links

• 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

Crossrefs

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

Programs

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

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