%I A005178 M3813
%S A005178 0,1,1,5,11,36,95,281,781,2245,6336,18061,51205,145601,413351,1174500,
%T A005178 3335651,9475901,26915305,76455961,217172736,616891945,1752296281,
%U A005178 4977472781,14138673395,40161441636,114079985111,324048393905
%N A005178 Number of domino tilings of 4 X (n-1) board.
%C A005178 Or, number of perfect matchings in graph P_4 X P_{n-1}.
%C A005178 a(0) = 0, a(1) = 1 by convention.
%C A005178 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 (deutsch(AT)duke.poly.edu), Oct 16 2006
%C A005178 This is a divisibility sequence; that is, if n divides m, then a(n) divides 
               a(m). [From T. D. Noe (noe(AT)sspectra.com), Dec 22 2008]
%C A005178 Contribution from Artur Jasinski (grafix(AT)csl.pl), Dec 20 2008: (Start)
%C A005178 All numbers in this sequence are:
%C A005178 congruent to 0 mod 100 if n is congruent to 14 or 29 mod 30
%C A005178 congruent to 1 mod 100 if n is congruent to 0 or 1 or 12 or 16 or 27 
               or 28 mod 30
%C A005178 congruent to 5 mod 100 if n is congruent to 2 or 11 or 17 or 26 mod 30
%C A005178 congruent to 11 mod 100 if n is congruent to 3 or 25 mod 30
%C A005178 congruent to 36 mod 100 if n is congruent to 4 or 9 or 19 or 24 mod 30
%C A005178 congruent to 45 mod 100 if n is congruent to 8 or 20 mod 30
%C A005178 congruent to 51 mod 100 if n is congruent to 13 or 15 mod 30
%C A005178 congruent to 61 mod 100 if n is congruent to 10 or 18 mod 30
%C A005178 congruent to 81 mod 100 if n is congruent to 6 or 7 or 21 or 22 mod 30
%C A005178 congruent to 95 mod 100 if n is congruent to 5 or 23 mod 30
%C A005178 (End)
%D A005178 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005178 F. Faase, On the number of specific spanning subgraphs of the graphs 
               G X P_n, Ars Combin. 49 (1998), 129-154.
%D A005178 S. Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino 
               tilings, Math. Gaz., to appear, 2008.
%D A005178 R. P. Stanley, Enumerative Combinatorics I, p. 292.
%H A005178 T. D. Noe, <a href="b005178.txt">Table of n, a(n) for n=0..200</a>
%H A005178 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 A005178 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamilton 
               cycles in product graphs</a>
%H A005178 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from 
               the counting program</a>
%H A005178 F. Faase, <a href="http://home.wxs.nl/~faase009/counting.html">Counting 
               Hamilton cycles in product graphs</a>
%H A005178 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A005178 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A005178 <a href="Sindx_Do.html#domino">Index entries for sequences related to 
               dominoes</a>
%F A005178 a(n)=a(n-1)+5a(n-2)+a(n-3)-a(n-4). G.f.: (1-x^2)/(1-x-5*x^2-x^3+x^4).
%F A005178 Lim_{n ->Inf} a(n)/a(n-1) = (1 + Sqrt(29) + Sqrt(14 + 2*Sqrt(29)) /4 
               = 2.84053619409... - Philippe DELEHAM, Jun 12 2005
%F A005178 G.f.: x(1-x^2)/(1-x-5x^2-x^3+x^4) [From T. D. Noe (noe(AT)sspectra.com), 
               Dec 22 2008]
%e A005178 For n=2 the graph is
%e A005178 . o-o-o-o
%e A005178 and there is one perfect tiling:
%e A005178 . o-o o-o
%e A005178 For n=3 the graph is
%e A005178 . o-o-o-o
%e A005178 . | | | |
%e A005178 . o-o-o-o
%e A005178 and there are five perfect tilings:
%e A005178 . o o o o
%e A005178 . | | | |
%e A005178 . o o o o
%e A005178 two like:
%e A005178 . o o o-o
%e A005178 . | | ...
%e A005178 . o o o-o
%e A005178 and this
%e A005178 . o-o o-o
%e A005178 . .......
%e A005178 . o-o o-o
%e A005178 and this
%e A005178 . o o-o o
%e A005178 . | ... |
%e A005178 . o o-o o
%p A005178 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 (deutsch(AT)duke.poly.edu), 
               Oct 16 2006
%p A005178 A005178:=-(-1-4*z-z**2+z**3)/(1-z-5*z**2-z**3+z**4); [Conjectured (correctly) 
               by S. Plouffe in his 1992 dissertation. Gives sequence apart from 
               an initial 1.]
%t A005178 CoefficientList[Series[x(1-x^2)/(1-x-5x^2-x^3+x^4), {x,0,30}], x] [From 
               T. D. Noe (noe(AT)sspectra.com), Dec 22 2008]
%t A005178 aa = {1, 1, 5, 11}; a0 = 1; a1 = 1; a2 = 5; a3 = 11; Do[a = a3 + 5*a2 
               + a1 - a0; AppendTo[aa, a]; a0 = a1; a1 = a2; a2 = a3; a3 = a, {n, 
               1, 100}]; aa [From Artur Jasinski (grafix(AT)csl.pl), Dec 20 2008]
%Y A005178 Row 4 of array A099390.
%Y A005178 For all matchings see A033507.
%Y A005178 Cf. A003775, A028468, A028469, A028470.
%Y A005178 Cf. A003757 [From T. D. Noe (noe(AT)sspectra.com), Dec 22 2008]
%Y A005178 Sequence in context: A055936 A164560 A054854 this_sequence A065315 A065317 
               A152563
%Y A005178 Adjacent sequences: A005175 A005176 A005177 this_sequence A005179 A005180 
               A005181
%K A005178 nonn,easy,new
%O A005178 0,4
%A A005178 N. J. A. Sloane (njas(AT)research.att.com), David Singmaster, Frans Faase 
               (Frans_LiXia(AT)wxs.nl)
%E A005178 Amalgamated with (former) A003692, Dec 30 1995
%E A005178 Changed name T. D. Noe (noe(AT)sspectra.com), Dec 22 2008
%E A005178 Prepended 0. - T. D. Noe (noe(AT)sspectra.com), Dec 22 2008
%E A005178 Edited by njas, Nov 15 2009