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, 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.
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).
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
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Recurrence from Faase's web page added by N. J. A. Sloane, Feb 03 2009
STATUS
approved