login
This site is supported by donations 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)
8
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

Peter Bala, Linear divisibility sequences and Chebyshev polynomials

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 Hamilton 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_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 to divisibility sequences

Index entries for sequences related to trees

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 A172204 A015673

Adjacent sequences:  A006235 A006236 A006237 * A006239 A006240 A006241

KEYWORD

nonn

AUTHOR

Frans J. Faase

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 22 23:15 EDT 2017. Contains 288633 sequences.