This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005178 Number of domino tilings of 4 X (n-1) board. (Formerly M3813) 26
 0, 1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281, 4977472781, 14138673395, 40161441636, 114079985111, 324048393905 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Or, number of perfect matchings in graph P_4 X P_{n-1}. a(0) = 0, a(1) = 1 by convention. 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 This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - T. D. Noe, Dec 22 2008 From Artur Jasinski, Dec 20 2008: (Start) All numbers in this sequence are: congruent to 0 mod 100 if n is congruent to 14 or 29 mod 30 congruent to 1 mod 100 if n is congruent to 0 or 1 or 12 or 16 or 27 or 28 mod 30 congruent to 5 mod 100 if n is congruent to 2 or 11 or 17 or 26 mod 30 congruent to 11 mod 100 if n is congruent to 3 or 25 mod 30 congruent to 36 mod 100 if n is congruent to 4 or 9 or 19 or 24 mod 30 congruent to 45 mod 100 if n is congruent to 8 or 20 mod 30 congruent to 51 mod 100 if n is congruent to 13 or 15 mod 30 congruent to 61 mod 100 if n is congruent to 10 or 18 mod 30 congruent to 81 mod 100 if n is congruent to 6 or 7 or 21 or 22 mod 30 congruent to 95 mod 100 if n is congruent to 5 or 23 mod 30 (End) 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 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). R. P. Stanley, Enumerative Combinatorics I, p. 292. LINKS T. D. Noe, Table of n, a(n) for n = 0..200 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, Results from the counting program Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 3. Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992. Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992. Simone Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino tilings, The Mathematical Gazette 92.524 (2008): 193-204. David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982. Herman Tulleken, Polyominoes 2.2: How they fit together, (2019). H. C Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277 H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume Li Zhou, Northwestern University Math Problem Solving Group, Christopher Carl Heckman and Jerry Minkus, Tiling 4-Rowed Rectangles with Dominoes: 11187, The American Mathematical Monthly 114 (2007): 554-556. Index entries for linear recurrences with constant coefficients, signature (1,5,1,-1). FORMULA a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4). G.f.: x*(1 - x^2)/(1 - x - 5*x^2 - x^3 + x^4). Lim_{n->inf} a(n)/a(n-1) = (1 + sqrt(29) + sqrt(14 + 2*sqrt(29)) /4 = 2.84053619409... - Philippe Deléham, Jun 12 2005 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 From Peter Bala, Mar 31 2014: (Start) 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. 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]. 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. See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End) EXAMPLE For n=2 the graph is . o-o-o-o and there is one perfect tiling: . o-o o-o For n=3 the graph is . o-o-o-o . | | | | . o-o-o-o and there are five perfect tilings: . o o o o . | | | | . o o o o two like: . o o o-o . | | ... . o o o-o and this . o-o o-o . ....... . o-o o-o and this . o o-o o . | ... | . o o-o o 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 MAPLE a:=1: a:=1: a:=5: a:=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 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 MATHEMATICA CoefficientList[Series[x(1-x^2)/(1-x-5x^2-x^3+x^4), {x, 0, 30}], x] (* T. D. Noe, Dec 22 2008 *) LinearRecurrence[{1, 5, 1, -1}, {0, 1, 1, 5}, 28] (* Robert G. Wilson v, Aug 08 2011 *) a = 0; a[n_] := Product[2(2+Cos[2j Pi/5]+Cos[2k Pi/n]), {k, 1, (n-1)/2}, {j, 1, 2}] // Round; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Aug 20 2018 *) PROG (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 */ CROSSREFS Row 4 of array A099390. For all matchings see A033507. Cf. A003775, A028468, A028469, A028470. Cf. A003757. - T. D. Noe, Dec 22 2008 Bisection (odd part) gives A188899. - Alois P. Heinz, Oct 28 2012 Column k=2 of A250662. Sequence in context: A054854 A188161 A323352 * A065315 A065317 A171268 Adjacent sequences:  A005175 A005176 A005177 * A005179 A005180 A005181 KEYWORD nonn,easy AUTHOR N. J. A. Sloane, David Singmaster, Frans J. Faase EXTENSIONS Amalgamated with (former) A003692, Dec 30 1995 Name changed and 0 prepended by T. D. Noe, Dec 22 2008 Edited by N. J. A. Sloane, Nov 15 2009 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 21 13:24 EDT 2019. Contains 328299 sequences. (Running on oeis4.)