login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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
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.
P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
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
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
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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:34 EDT 2024. Contains 371265 sequences. (Running on oeis4.)