login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003779 Number of spanning trees in P_5 x P_n. 4

%I

%S 1,209,30305,4140081,557568000,74795194705,10021992194369,

%T 1342421467113969,179796299139278305,24080189412483072000,

%U 3225041354570508955681,431926215138756947267505,57847355494807961811035009,7747424602888405489208931601

%N Number of spanning trees in P_5 x P_n.

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

%C 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

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

%H P. Raff, <a href="/A003779/b003779.txt">Table of n, a(n) for n = 1..200</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H P. Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>.

%H P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/5/12-13-24-35/index.xml">Analysis of the Number of Spanning Trees of P_5 x P_n.</a> Contains sequence, recurrence, generating function, and more.

%H P. Raff, <a href="http://www.myraff.com/projects/spanning-trees-in-grid-graphs">Analysis of the Number of Spanning Trees of Grid Graphs</a>.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

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

%F - 11936 a(n-2)

%F + 274208 a(n-3)

%F - 3112032 a(n-4)

%F + 19456019 a(n-5)

%F - 70651107 a(n-6)

%F + 152325888 a(n-7)

%F - 196664896 a(n-8)

%F + 152325888 a(n-9)

%F - 70651107 a(n-10)

%F + 19456019 a(n-11)

%F - 3112032 a(n-12)

%F + 274208 a(n-13)

%F - 11936 a(n-14)

%F + 209 a(n-15)

%F - a(n-16)

%F [Modified by _Paul Raff_, Oct 30 2009]

%F 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).

%F From _Peter Bala_, Apr 26 2014: (Start)

%F 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).

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

%p 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

%t 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 *)

%o (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

%Y A row of A116469. Bisection of A189005.

%Y Cf. A143699, A159764, A241606.

%K nonn,easy

%O 1,2

%A _Frans J. Faase_

%E Recurrence from Faase's web page added by _N. J. A. Sloane_, Feb 03 2009

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 19:30 EST 2020. Contains 332047 sequences. (Running on oeis4.)