The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A006238 Complexity of (or spanning trees in) a 3 X n grid. (Formerly M4986) 10
 1, 15, 192, 2415, 30305, 380160, 4768673, 59817135, 750331584, 9411975375, 118061508289, 1480934568960, 18576479568193, 233018797965135, 2922930580320960, 36664523428884015, 459910778352898337, 5769007865476035840, 72365017995700730081, 907729015392142395375 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS a(n) is a divisibility sequence - m divides n implies that a(m) divides a(n). - Paul Raff, Mar 06 2009 Also number of domino tilings of the 5 X (2n-1) rectangle with upper left corner removed.  For n=2 the 15 domino tilings of the 5 X 3 rectangle with upper left corner removed are: . .___. . .___. . .___. . .___. . .___. . .___. . .___. . .___. ._|___| ._| | | ._|___| ._|___| ._|___| ._| | | ._| | | ._|___| | |___| | |_|_| | | | | | |___| | |___| | |_|_| | |_|_| | | | | |_|___| |_|___| |_|_|_| |_| | | |_|___| |_| | | |_|___| |_|_|_| | |___| | |___| | |___| | |_|_| | | | | | |_|_| | | | | | | | | |_|___| |_|___| |_|___| |_|___| |_|_|_| |_|___| |_|_|_| |_|_|_| . .___. . .___. . .___. . .___. . .___. . .___. . .___. ._|___| ._|___| ._|___| ._|___| ._|___| ._|___| ._| | | |___| | | | | | |___| | |___| | |___| | | |___| | |_|_| |___|_| |_|_|_| | | |_| |___|_| |___|_| |_|___| |_|___| |___| | |___| | |_|_| | | | | | | |___| |___| | |___| | |___|_| |___|_| |___|_| |_|_|_| |_|___| |___|_| |___|_| - Alois P. Heinz, Apr 14 2011 REFERENCES F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154. G. Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe, 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. P. Raff, Analysis of the Number of Spanning Trees of P_3 x P_n. Contains sequence, recurrence, generating function, and more. Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277 Index entries for linear recurrences with constant coefficients, signature (15,-32,15,-1). FORMULA a(n) = 15a(n-1) - 32a(n-2) + 15a(n-3) - a(n-4), n>4. G.f.: -x(x^2-1)/(x^4-15x^3+32x^2-15x+1). - Paul Raff, Mar 06 2009 a(n)=A001906(n)*A004254(n). - R. J. Mathar, Jun 03 2009 From Peter Bala, Mar 25 2014: (Start) a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (15 + sqrt(105))/4 and beta = (15 - sqrt(105))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind. a(n) = the bottom left entry of the 2X2 matrix T(n, M), where M is the 2X2 matrix [0, -15/2; 1, 15/2]. See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End) a(n)=(A003775(n+1)+A003775(n-2))/24-(A003775(n)+A003775(n-1))/3, n>1. - Sergey Perepechko, Apr 26 2016 MAPLE a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|15|-32|15>>^n. <<1, 0, 1, 15>>)[2, 1]: seq(a(n), n=1..30);  # Alois P. Heinz, Apr 14 2011 MATHEMATICA LinearRecurrence[{15, -32, 15, -1}, {1, 15, 192, 2415}, 30] (* Harvey P. Dale, May 14 2013 *) CROSSREFS Row 3 of A116469. A100047. Sequence in context: A038339 A051545 A220528 * A201883 A324357 A172204 Adjacent sequences:  A006235 A006236 A006237 * A006239 A006240 A006241 KEYWORD nonn AUTHOR STATUS approved

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

Last modified September 24 19:49 EDT 2022. Contains 356949 sequences. (Running on oeis4.)