A139400 Number of spanning trees in the graph P_6 x P_n.

1, 780, 380160, 170537640, 74795194705, 32565539635200, 14143261515284447, 6136973985625588560, 2662079368040434932480, 1154617875754582889149500, 500769437567956298239402223, 217185579535490113365186969600

Offset: 1

Author

Paul Raff, Jun 09 2008; corrected recurrence Feb 03 2009

Keywords

• easy
• nonn

Comments

Also number of domino tilings of the 11 X (2n-1) rectangle with upper left corner removed. - Alois P. Heinz, Apr 14 2011

A linear divisibility sequence of order 32; a(n) divides a(m) whenever n divides m. It is the product of four linear divisibility sequences - three Lucas sequences of order 2 and one linear divisibility sequence of order 4. - Peter Bala, Apr 27 2014

Examples

			a(2) = 780, as can be verified from the seventh entry of A001353, which corresponds to the number of spanning trees of the same graph.
		

Links

• Paul Raff, Table of n, a(n) for n = 1..208
• Paul Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
• Index to divisibility sequences
• Index entries for linear recurrences with constant coefficients, signature (780, -194881, 22377420, -1419219792, 55284715980, -1410775106597, 24574215822780, -300429297446885, 2629946465331120, -16741727755133760, 78475174345180080, -273689714665707178, 716370537293731320, -1417056251105102122, 2129255507292156360, -2437932520099475424, 2129255507292156360, -1417056251105102122, 716370537293731320, -273689714665707178, 78475174345180080, -16741727755133760, 2629946465331120, -300429297446885, 24574215822780, -1410775106597, 55284715980, -1419219792, 22377420, -194881, 780, -1).

Crossrefs

Row m=6 of A116469.

Bisection of A210724 (odd part). A001353, A001906, A004254, A159764, A161498.

Programs

Maple

seq(resultant(simplify(ChebyshevU(5, (x-4)*(1/2))), simplify(ChebyshevU(n-1, (1/2)*x)), x), n = 1 .. 12); # Peter Bala, Apr 27 2014

Mathematica

Array[Resultant[ChebyshevU[5, x/2-2], ChebyshevU[#-1, x/2], x] &, 20] (* Paolo Xausa, Mar 17 2024, after Peter Bala *)

Formula

a(n) = 780 a(n-1) - 194881 a(n-2) + 22377420 a(n-3) - 1419219792 a(n-4) + 55284715980 a(n-5) - 1410775106597 a(n-6) + 24574215822780 a(n-7) - 300429297446885 a(n-8) + 2629946465331120 a(n-9) - 16741727755133760 a(n-10)

+ 78475174345180080 a(n-11) - 273689714665707178 a(n-12) + 716370537293731320 a(n-13) - 1417056251105102122 a(n-14) + 2129255507292156360 a(n-15) - 2437932520099475424 a(n-16) + 2129255507292156360 a(n-17)

- 1417056251105102122 a(n-18) + 716370537293731320 a(n-19) - 273689714665707178 a(n-20) + 78475174345180080 a(n-21) - 16741727755133760 a(n-22) + 2629946465331120 a(n-23) - 300429297446885 a(n-24) + 24574215822780 a(n-25) - 1410775106597 a(n-26) + 55284715980 a(n-27) - 1419219792 a(n-28) + 22377420 a(n-29) - 194881 a(n-30) + 780 a(n-31) - a(n-32).

From Peter Bala, Apr 27 2014: (Start)

a(n) = Resultant( U(5,(x-4)/2), U(n-1,x/2) ), where U(n,x) denotes the Chebyshev polynomial of the second kind. The polynomial U(5,(x-4)/2) = x^5 - 20*x^4 + 156*x^3 - 592*x^2 + 1091*x - 780 (see A159764) has zeros z_1 = 3, z_2 = 4, z_3 = 5, z_4 = 4 + sqrt(3) and z_5 = 4 - sqrt(3). Hence a(n) = U(n-1,3/2)*U(n-1,2)*U(n-1,5/2)*U(n-1,1/2*(4 + sqrt(3)))*U(n-1,1/2*(4 - sqrt(3))).

a(n) = A001906(n)*A001353(n)*A004254(n)*A161498(n). (End)