0,4

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 (deutsch(AT)duke.poly.edu), Oct 16 2006

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]

Contribution from Artur Jasinski (grafix(AT)csl.pl), 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)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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., to appear, 2008.

R. P. Stanley, Enumerative Combinatorics I, p. 292.

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

F. Faase, Counting Hamilton cycles in product graphs

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.

S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

Index entries for sequences related to dominoes

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

Lim_{n ->Inf} a(n)/a(n-1) = (1 + Sqrt(29) + Sqrt(14 + 2*Sqrt(29)) /4 = 2.84053619409... - Philippe DELEHAM, Jun 12 2005

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]

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

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.]

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]

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]

Row 4 of array A099390.

For all matchings see A033507.

Cf. A003775, A028468, A028469, A028470.

Cf. A003757 [From T. D. Noe (noe(AT)sspectra.com), Dec 22 2008]

Sequence in context: A055936 A164560 A054854 this_sequence A065315 A065317 A152563

Adjacent sequences: A005175 A005176 A005177 this_sequence A005179 A005180 A005181

nonn,easy,new

N. J. A. Sloane (njas(AT)research.att.com), David Singmaster, Frans Faase (Frans_LiXia(AT)wxs.nl)

Amalgamated with (former) A003692, Dec 30 1995

Changed name T. D. Noe (noe(AT)sspectra.com), Dec 22 2008

Prepended 0. - T. D. Noe (noe(AT)sspectra.com), Dec 22 2008

Edited by njas, Nov 15 2009