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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002478 Bisection of A000930.
(Formerly M2572 N1017)
38
1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201, 58425, 125491, 269542, 578949, 1243524, 2670964, 5736961, 12322413, 26467299, 56849086, 122106097, 262271568, 563332848, 1209982081, 2598919345, 5582216355, 11990037126, 25753389181 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of ways to tile a 3 X n region with 1 X 1, 2 X 2 and 3 X 3 tiles.

Number of ternary words with subwords (0,0), (0,1) and (1,1) not allowed. - Olivier Gérard, Aug 28 2012

Diagonal sums of A063967. - Paul Barry, Nov 09 2005

Row sums of number triangle A116088. - Paul Barry, Feb 04 2006

Sequence is identical to its second differences negated, minus the first 3 terms. - Paul Curtz, Feb 10 2008

a(n) = term (3,3) in the 3x3 matrix [0,1,0; 0,0,1; 1,2,1]^n. - Gary W. Adamson, May 30 2008

a(n)/a(n-1) tends to 2.147899035..., an eigenvalue of the matrix and a root to x^3 - x^2 - 2x - 1 = 0. - Gary W. Adamson, May 30 2008

INVERT transform of (1, 2, 1, 0, 0, 0,...) = (1, 3, 6, 13, 28,...); such that (1, 2, 1, 0, 0, 0,...) convolved with (1, 1, 3, 6, 13, 28, 0, 0, 0,...) shifts to the left. - Gary W. Adamson, Apr 18 2010

a(n) is the top left entry in the n-th power of the 3X3 matrix [1, 1, 1; 1, 0, 1; 1, 0, 0] or of the 3X3 matrix [1, 1, 1; 1, 0, 0; 1, 1, 0]. - R. J. Mathar, Feb 03 2014

REFERENCES

L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 322.

S. Heubach, Tiling an m X n Area with Squares of Size up to k X k (m<=5), Congressus Numerantium 140 (1999), pp. 43-64.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

LINKS

T. D. Noe, Table of n, a(n) for n = 0..300

E. Deutsch, Counting tilings with L-tiles and squares, Problem 10877, Amer. Math. Monthly, 110 (March 2003), 245-246.

L. Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 412

Milan Janjic, Pascal Triangle and Restricted Words, arXiv:1705.02497 [math.CO], 2017.

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 19 (halved...)

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.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

Index entries for linear recurrences with constant coefficients, signature (1,2,1).

FORMULA

G.f. 1 / (1-x-2*x^2-x^3 ). [Simon Plouffe in his 1992 dissertation.]

a(n) = a(n-1)+2a(n-2)+a(n-3).

a(n) = sum{k=0..n, binomial(2n-2k, k)}. - Paul Barry, Nov 13 2004

a(n) = sum{k=0..floor(n/2), sum{j=0..n-k, C(j, n-k-j)C(j, k)}}. - Paul Barry, Nov 09 2005

a(n) = sum{k=0..n, C(2k,n-k)}=sum{k=0..n, C(n,k)C(3k,n)/C(3k,k)}. - Paul Barry, Feb 04 2006

EXAMPLE

a(3)=6 as there is one tiling of a 3 X 3 region with only 1 X 1 tiles, 4 tilings with exactly one 2 X 2 tile and 1 tiling consisting of the 3 X 3 tile.

MATHEMATICA

f[ A_ ] := Module[ {til = A}, AppendTo[ til, A[ [ -1 ] ] + 2A[ [ -2 ] ] + A[ [ -3 ] ] ] ]; NumOfTilings[ n_ ] := Nest[ f, {1, 1, 3}, n - 2 ]; NumOfTilings[ 30 ]

LinearRecurrence[{1, 2, 1}, {1, 1, 3}, 40] (* Vladimir Joseph Stephan Orlovsky, Jan 28 2012 *)

PROG

(PARI) a(n)=([0, 1, 0; 0, 0, 1; 1, 2, 1]^n*[1; 1; 3])[1, 1] \\ Charles R Greathouse IV, Apr 08 2016

CROSSREFS

Cf. A054856, A054857, A025234, A078007, A078039, A226546, A077936 (INVERT transform), A008346 (inverse INVERT transform).

Sequence in context: A182137 A106461 A095768 * A106496 A052933 A071014

Adjacent sequences:  A002475 A002476 A002477 * A002479 A002480 A002481

KEYWORD

easy,nonn,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

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 February 25 14:46 EST 2018. Contains 299654 sequences. (Running on oeis4.)