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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003696 Number of spanning trees in P_4 X P_n. 4
1, 56, 2415, 100352, 4140081, 170537640, 7022359583, 289143013376, 11905151192865, 490179860527896, 20182531537581071, 830989874753525760, 34214941811800329425, 1408756312731277540744 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

A linear divisibility sequence of order 8; a(n) divides a(m) whenever n divides m. It is the product of a 2nd-order Lucas sequence and a 4-th order linear divisibility sequence. - Peter Bala, Apr 27 2014

REFERENCES

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..200

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

P. Raff, Spanning Trees in Grid Graphs.

P. Raff, Analysis of the Number of Spanning Trees of P_4 x P_n. Contains sequence, recurrence, generating function, and more.

Index entries for sequences related to trees

FORMULA

a(1) = 1,

a(2) = 56,

a(3) = 2415,

a(4) = 100352,

a(5) = 4140081,

a(6) = 170537640,

a(7) = 7022359583,

a(8) = 289143013376 and

a(n) = 56a(n-1) - 672a(n-2) + 2632a(n-3) - 4094a(n-4) + 2632a(n-5) - 672a(n-6) + 56a(n-7) - a(n-8).

G.f.: x(x^6-49x^4+112x^3-49x^2+1) / (x^8-56x^7 +672x^6-2632x^5 +4094x^4 -2632x^3 +672x^2-56x+1). [From Paul Raff, Mar 06 2009]

From Peter Bala, Apr 27 2014: (Start)

a(n) = Resultant( U(3,(x-4)/2),U(n-1,x/2) ), where U(n,x) denotes the Chebyshev polynomial of the second kind. The polynomial U(3,(x-4)/2) = x^3 - 12*x^2 + 46*x - 56 (see A159764) has zeros z_1 = 4, z_2 = 4 + sqrt(2) and z_3 = 4 - sqrt(2). Hence a(n) = U(n-1,2)*U(n-1,1/2*(4 + sqrt(2)))*U(n-1,1/2*(4 - sqrt(2))).

a(n) = A001353(n)*A161158(n-1). (End)

MAPLE

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

CROSSREFS

A row of A116469. - N. J. A. Sloane, May 27 2012

Bisection of A189004. - Alois P. Heinz, Sep 20 2012

A001353, A161158, A159764.

Sequence in context: A221398 A124101 A198948 * A199709 A205227 A224176

Adjacent sequences:  A003693 A003694 A003695 * A003697 A003698 A003699

KEYWORD

nonn,easy

AUTHOR

Frans J. Faase

EXTENSIONS

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 20 18:53 EDT 2014. Contains 248371 sequences.