|
|
A139400
|
|
Number of spanning trees in the graph P_6 x P_n.
|
|
6
|
|
|
1, 780, 380160, 170537640, 74795194705, 32565539635200, 14143261515284447, 6136973985625588560, 2662079368040434932480, 1154617875754582889149500, 500769437567956298239402223, 217185579535490113365186969600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
|
|
LINKS
|
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).
|
|
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).
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))).
|
|
EXAMPLE
|
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.
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,changed
|
|
AUTHOR
|
Paul Raff, Jun 09 2008; corrected recurrence Feb 03 2009
|
|
STATUS
|
approved
|
|
|
|