login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A139400 Number of spanning trees in the graph P_6 x P_n. 5
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

P. Raff, Table of n, a(n) for n = 1..208

Paul Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO]

Index to divisibility sequences

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)

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

CROSSREFS

Row m=6 of A116469.

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

Sequence in context: A259924 A135198 A250952 * A115467 A020231 A141390

Adjacent sequences:  A139397 A139398 A139399 * A139401 A139402 A139403

KEYWORD

easy,nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 02:46 EDT 2017. Contains 286909 sequences.