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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003779 Number of spanning trees in P_5 x P_n. 4
1, 209, 30305, 4140081, 557568000, 74795194705, 10021992194369, 1342421467113969, 179796299139278305, 24080189412483072000, 3225041354570508955681, 431926215138756947267505, 57847355494807961811035009, 7747424602888405489208931601 (list; graph; refs; listen; history; text; internal format)
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.

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

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 January 19 20:41 EST 2020. Contains 331066 sequences. (Running on oeis4.)