A006238 Complexity of (or spanning trees in) a 3 X n grid.

1, 15, 192, 2415, 30305, 380160, 4768673, 59817135, 750331584, 9411975375, 118061508289, 1480934568960, 18576479568193, 233018797965135, 2922930580320960, 36664523428884015, 459910778352898337, 5769007865476035840, 72365017995700730081, 907729015392142395375

Offset: 1

Author

Frans J. Faase

Keywords

• nonn

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.
• 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 Hamiltonian cycles in product graphs
• F. Faase, Results from the counting program
• Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
• 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
• Index to divisibility sequences
• Index entries for sequences related to trees
• Index entries for linear recurrences with constant coefficients, signature (15,-32,15,-1).

Crossrefs

Row 3 of A116469. A100047.

Programs

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 *)

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