A003779 Number of spanning trees in P_5 x P_n.

1, 209, 30305, 4140081, 557568000, 74795194705, 10021992194369, 1342421467113969, 179796299139278305, 24080189412483072000, 3225041354570508955681, 431926215138756947267505, 57847355494807961811035009, 7747424602888405489208931601

Offset

1,2

Comments

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

A linear divisibility sequence of order 16; a(n) divides a(m) whenever n divides m. It is the product of two 4th-order linear divisibility sequences A143699 and A241606. - Peter Bala, Apr 26 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

P. Raff, 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 Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

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

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

P. Raff, Analysis of the Number of Spanning Trees of Grid Graphs.

Index to divisibility sequences

Index entries for sequences related to trees

Formula

a(n) = 209 a(n-1)

- 11936 a(n-2)

+ 274208 a(n-3)

- 3112032 a(n-4)

+ 19456019 a(n-5)

- 70651107 a(n-6)

+ 152325888 a(n-7)

- 196664896 a(n-8)

+ 152325888 a(n-9)

- 70651107 a(n-10)

+ 19456019 a(n-11)

- 3112032 a(n-12)

+ 274208 a(n-13)

- 11936 a(n-14)

+ 209 a(n-15)

- a(n-16)

[Modified by Paul Raff, Oct 30 2009]

G.f.: -x(x^14-1440x^12+26752x^11 -185889x^10+574750x^9-708928x^8 +708928x^6-574750x^5+185889x^4 -26752x^3+1440x^2-1) / (x^16-209x^15 +11936x^14 -274208x^13+3112032x^12-19456019x^11 +70651107x^10 -152325888x^9 +196664896x^8 -152325888x^7+70651107x^6 -19456019x^5 +3112032x^4-274208x^3+11936x^2-209x+1).

From Peter Bala, Apr 26 2014: (Start)

a(n) = Resultant(U(4,(x-4)/2),U(n-1,x/2)), where U(n,x) denotes the Chebyshev polynomial of the second kind. The polynomial U(4,(x-4)/2) = 209 - 232*x + 93*x^2 - 16*x^3 + x^4 (see A159764) has zeros z_1 = (9 + sqrt(5))/2, z_2 = (9 - sqrt(5))/2, z_3 = (7 + sqrt(5))/2 and z_4 = (7 - sqrt(5))/2. Thus a(n) = U(n-1,1/2*z_1)*U(n-1,1/2*z_2)*U(n-1,1/2*z_3)*U(n-1,1/2*z_4).

a(n) = A143699(n)*A241606(n). (End)

Maple

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

Mathematica

a[n_] := 256^(n-1)*Product[Sin[(h*Pi)/10]^2 + Sin[(k*Pi)/(2*n)]^2, {h, 1, 4}, {k, 1, n-1}]; Table[a[n]//Round, {n, 1, 14}] (* Jean-François Alcover, Apr 28 2014 *)

Prog

(PARI) Vec(-x*(x^14-1440*x^12+26752*x^11-185889*x^10+574750*x^9-708928*x^8+708928*x^6-574750*x^5+185889*x^4-26752*x^3+1440*x^2-1)/(x^16-209*x^15+11936*x^14-274208*x^13+3112032*x^12-19456019*x^11+70651107*x^10-152325888*x^9+196664896*x^8-152325888*x^7+70651107*x^6-19456019*x^5+3112032*x^4-274208*x^3+11936*x^2-209*x+1)+O(x^99)) \\ Charles R Greathouse IV, Nov 13 2015

Crossrefs

A row of A116469. Bisection of A189005.

Cf. A143699, A159764, A241606.

Sequence in context: A317463 A029554 A203458 * A268659 A265682 A071379

Adjacent sequences: A003776 A003777 A003778 * A003780 A003781 A003782

Keyword

nonn,easy

Author

Frans J. Faase

Extensions

Recurrence from Faase's web page added by N. J. A. Sloane, Feb 03 2009

Status

approved