|
%I #52 Aug 23 2023 09:37:34
%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>, arXiv:0809.2551 [math.CO], 2008.
%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
| 