|
%I M3813 #137 Apr 13 2022 13:25:17
%S 0,1,1,5,11,36,95,281,781,2245,6336,18061,51205,145601,413351,1174500,
%T 3335651,9475901,26915305,76455961,217172736,616891945,1752296281,
%U 4977472781,14138673395,40161441636,114079985111,324048393905
%N Number of domino tilings of 4 X (n-1) board.
%C Or, number of perfect matchings in graph P_4 X P_{n-1}.
%C a(0) = 0, a(1) = 1 by convention.
%C It is easy to see that the g.f. for indecomposable tilings, i.e., those that cannot be split vertically into smaller tilings, is g = x + 4x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 2x^7 + 3x^8 + ... = x + 4x^2 + x^3*(2+3x)/(1-x^2); then g.f. = 1/(1-g) = (1-x^2)/(1-x-5x^2-x^3+x^4). - _Emeric Deutsch_, Oct 16 2006
%C This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - _T. D. Noe_, Dec 22 2008
%C From _Artur Jasinski_, Dec 20 2008: (Start)
%C All numbers in this sequence are:
%C congruent to 0 mod 100 if n is congruent to 14 or 29 mod 30
%C congruent to 1 mod 100 if n is congruent to 0 or 1 or 12 or 16 or 27 or 28 mod 30
%C congruent to 5 mod 100 if n is congruent to 2 or 11 or 17 or 26 mod 30
%C congruent to 11 mod 100 if n is congruent to 3 or 25 mod 30
%C congruent to 36 mod 100 if n is congruent to 4 or 9 or 19 or 24 mod 30
%C congruent to 45 mod 100 if n is congruent to 8 or 20 mod 30
%C congruent to 51 mod 100 if n is congruent to 13 or 15 mod 30
%C congruent to 61 mod 100 if n is congruent to 10 or 18 mod 30
%C congruent to 81 mod 100 if n is congruent to 6 or 7 or 21 or 22 mod 30
%C congruent to 95 mod 100 if n is congruent to 5 or 23 mod 30
%C (End)
%C This is the case P1 = 1, P2 = -7, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - _Peter Bala_, Mar 31 2014
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics I, p. 292.
%H T. D. Noe, <a href="/A005178/b005178.txt">Table of n, a(n) for n = 0..200</a>
%H Steve Butler, Jason Ekstrand, Steven Osborne, <a href="https://doi.org/10.1007/978-3-030-37853-0_5">Counting Tilings by Taking Walks in a Graph</a>, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 158.
%H Curtis Cooper and Robert E. Kennedy, <a href="https://www.fq.math.ca/Scanned/32-2/elementary32-2.pdf">Problem B-735: Soln 1</a>, <a href="https://www.fq.math.ca/Scanned/32-4/elementary32-4.pdf">Problem B-735: Soln 2</a>, Square Root of a Recurrence, The Fibonacci Quarterly, 32(2):185-186, May 1994, and 32(4):374-375, Aug 1994.
%H 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 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H Vladimir Victorovich Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 3.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Simone Rinaldi and D. G. Rogers, <a href="http://www.jstor.org/stable/27821767">Indecomposability: polyominoes and polyomino tilings</a>, The Mathematical Gazette 92.524 (2008): 193-204.
%H David Singmaster, <a href="/A005178/a005178.pdf">Letter to N. J. A. Sloane</a>, Oct 3 1982.
%H Thotsaporn ”Aek” Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/57-5/thanatipanonda.pdf">Statistics of Domino Tilings on a Rectangular Board</a>, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
%H Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).
%H H. C Williams, R. K. Guy, <a href="http://dx.doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory 7 (5) (2011) 1255-1277
%H H. C. Williams and R. K. Guy, <a href="http://www.emis.de/journals/INTEGERS/papers/a17self/a17self.pdf">Some Monoapparitic Fourth Order Linear Divisibility Sequences</a> Integers, Volume 12A (2012) The John Selfridge Memorial Volume.
%H Li Zhou, Northwestern University Math Problem Solving Group, Christopher Carl Heckman and Jerry Minkus, <a href="http://www.jstor.org/stable/27642267">Tiling 4-Rowed Rectangles with Dominoes: 11187</a>, The American Mathematical Monthly 114 (2007): 554-556.
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,5,1,-1).
%F a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4).
%F G.f.: x*(1 - x^2)/(1 - x - 5*x^2 - x^3 + x^4).
%F Limit_{n->infinity} a(n)/a(n-1) = (1 + sqrt(29) + sqrt(14 + 2*sqrt(29)) /4 = 2.84053619409... - _Philippe Deléham_, Jun 12 2005
%F a(n) = (5*sqrt(29)/145)*(((1+sqrt(29)+sqrt(14+2*sqrt(29)))/4)^n+((1+sqrt(29)-sqrt(14+2*sqrt(29)))/4)^n-((1-sqrt(29)+sqrt(14-2*sqrt(29)))/4)^n-((1-sqrt(29)-sqrt(14-2*sqrt(29)))/4)^n). - _Tim Monahan_, Jul 30 2011
%F From _Peter Bala_, Mar 31 2014: (Start)
%F a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(29))/4 and beta = (1 - sqrt(29))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
%F a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 7/4; 1, 1/2].
%F a(n) = U(n-1,i*(1 + sqrt(5))/4)*U(n-1,i*(1 - sqrt(5))/4), where U(n,x) denotes the Chebyshev polynomial of the second kind.
%F See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
%F a(n) = A129113(n+2) - A129113(n). - _R. J. Mathar_, May 03 2021
%e For n=2 the graph is
%e . o-o-o-o
%e and there is one perfect tiling:
%e . o-o o-o
%e For n=3 the graph is
%e . o-o-o-o
%e . | | | |
%e . o-o-o-o
%e and there are five perfect tilings:
%e . o o o o
%e . | | | |
%e . o o o o
%e two like:
%e . o o o-o
%e . | | ...
%e . o o o-o
%e and this
%e . o-o o-o
%e . .......
%e . o-o o-o
%e and this
%e . o o-o o
%e . | ... |
%e . o o-o o
%e a(n+1)=r(n)-r(n-2), r(n)=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n), n>1. - _Vladimir Kruchinin_, Sep 08 2010
%p a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=11: for n from 4 to 26 do a[n]:=a[n-1]+5*a[n-2]+a[n-3]-a[n-4] od: seq(a[n],n=0..26); # _Emeric Deutsch_, Oct 16 2006
%p A005178:=-(-1-4*z-z**2+z**3)/(1-z-5*z**2-z**3+z**4) # conjectured (correctly) by _Simon Plouffe_ in his 1992 dissertation; gives sequence apart from an initial 1
%t CoefficientList[Series[x(1-x^2)/(1-x-5x^2-x^3+x^4), {x,0,30}], x] (* _T. D. Noe_, Dec 22 2008 *)
%t LinearRecurrence[{1, 5, 1, -1}, {0, 1, 1, 5}, 28] (* _Robert G. Wilson v_, Aug 08 2011 *)
%t a[0] = 0; a[n_] := Product[2(2+Cos[2j Pi/5]+Cos[2k Pi/n]), {k, 1, (n-1)/2}, {j, 1, 2}] // Round;
%t Table[a[n], {n, 0, 27}] (* _Jean-François Alcover_, Aug 20 2018 *)
%o (Maxima) r(n):=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n); a(n):=r(n)-r(n-2); /* _Vladimir Kruchinin_, Sep 08 2010 */
%Y Row 4 of array A099390.
%Y For all matchings see A033507.
%Y Cf. A003775, A028468, A028469, A028470.
%Y Cf. A003757. - _T. D. Noe_, Dec 22 2008
%Y Bisection (odd part) gives A188899. - _Alois P. Heinz_, Oct 28 2012
%Y Column k=2 of A250662.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_, David Singmaster, _Frans J. Faase_
%E Amalgamated with (former) A003692, Dec 30 1995
%E Name changed and 0 prepended by _T. D. Noe_, Dec 22 2008
%E Edited by _N. J. A. Sloane_, Nov 15 2009
| 