cp's OEIS Frontend

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

%I A006238 M4986 #62 May 19 2024 09:42:44
%S A006238 1,15,192,2415,30305,380160,4768673,59817135,750331584,9411975375,
%T A006238 118061508289,1480934568960,18576479568193,233018797965135,
%U A006238 2922930580320960,36664523428884015,459910778352898337,5769007865476035840,72365017995700730081,907729015392142395375
%N A006238 Complexity of (or spanning trees in) a 3 X n grid.
%C A006238 a(n) is a divisibility sequence - m divides n implies that a(m) divides a(n). - _Paul Raff_, Mar 06 2009
%C A006238 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:
%C A006238 . .___. . .___. . .___. . .___. . .___. . .___. . .___. . .___.
%C A006238 ._|___| ._| | | ._|___| ._|___| ._|___| ._| | | ._| | | ._|___|
%C A006238 | |___| | |_|_| | | | | | |___| | |___| | |_|_| | |_|_| | | | |
%C A006238 |_|___| |_|___| |_|_|_| |_| | | |_|___| |_| | | |_|___| |_|_|_|
%C A006238 | |___| | |___| | |___| | |_|_| | | | | | |_|_| | | | | | | | |
%C A006238 |_|___| |_|___| |_|___| |_|___| |_|_|_| |_|___| |_|_|_| |_|_|_|
%C A006238 . .___. . .___. . .___. . .___. . .___. . .___. . .___.
%C A006238 ._|___| ._|___| ._|___| ._|___| ._|___| ._|___| ._| | |
%C A006238 |___| | | | | | |___| | |___| | |___| | | |___| | |_|_|
%C A006238 |___|_| |_|_|_| | | |_| |___|_| |___|_| |_|___| |_|___|
%C A006238 |___| | |___| | |_|_| | | | | | | |___| |___| | |___| |
%C A006238 |___|_| |___|_| |___|_| |_|_|_| |_|___| |___|_| |___|_|
%C A006238 - _Alois P. Heinz_, Apr 14 2011
%D A006238 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%D A006238 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006238 T. D. Noe, <a href="/A006238/b006238.txt">Table of n, a(n) for n = 1..200</a>
%H A006238 Peter Bala, <a href="/A100047/a100047.pdf">Linear divisibility sequences and Chebyshev polynomials</a>
%H A006238 F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H A006238 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A006238 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A006238 Germain Kreweras, <a href="https://doi.org/10.1016/0095-8956(78)90021-7">Complexité et circuits Eulériens dans les sommes tensorielles de graphes</a>, J. Combin. Theory, B 24 (1978), 202-212.
%H A006238 P. Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008.
%H A006238 P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/3/12-13/index.xml">Analysis of the Number of Spanning Trees of P_3 x P_n</a>. Contains sequence, recurrence, generating function, and more.
%H A006238 Hugh Williams, R. K. Guy, <a href="http://dx.doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
%H A006238 <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H A006238 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A006238 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (15,-32,15,-1).
%F A006238 a(n) = 15a(n-1) - 32a(n-2) + 15a(n-3) - a(n-4), n>4.
%F A006238 G.f.: -x(x^2-1)/(x^4-15x^3+32x^2-15x+1). - _Paul Raff_, Mar 06 2009
%F A006238 a(n) = A001906(n)*A004254(n). - _R. J. Mathar_, Jun 03 2009
%F A006238 From _Peter Bala_, Mar 25 2014: (Start)
%F A006238 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.
%F A006238 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].
%F A006238 See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
%F A006238 a(n) = (A003775(n+1)+A003775(n-2))/24-(A003775(n)+A003775(n-1))/3, n>1. - _Sergey Perepechko_, Apr 26 2016
%p A006238 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
%t A006238 LinearRecurrence[{15,-32,15,-1},{1,15,192,2415},30] (* _Harvey P. Dale_, May 14 2013 *)
%Y A006238 Row 3 of A116469. A100047.
%K A006238 nonn
%O A006238 1,2
%A A006238 _Frans J. Faase_