Search: id:A005178 Results 1-1 of 1 results found. %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, Table of n, a(n) for n=0..200 %H A005178 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. %H A005178 F. Faase, Counting Hamilton cycles in product graphs %H A005178 F. Faase, Results from the counting program %H A005178 F. Faase, Counting Hamilton cycles in product graphs %H A005178 S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992. %H A005178 S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992. %H A005178 Index entries for sequences related to dominoes %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 %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 N. J. A. Sloane, Nov 15 2009 Search completed in 0.002 seconds