login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005178 Number of domino tilings of 4 X (n-1) board.
(Formerly M3813)
20
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.

S. Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino tilings, Math. Gaz., 92 (July) (2008) 192-204.

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, Counting Hamilton cycles in product graphs

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.

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

Index to divisibility sequences

Index entries for sequences related to dominoes

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[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

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 *)

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: A164560 A054854 A188161 * 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

Changed name, prepended 0. - 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 11:51 EDT 2017. Contains 287205 sequences.