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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052980 Expansion of (1 - x)/(1 - 2*x - x^3). 17
1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255, 2768, 6105, 13465, 29698, 65501, 144467, 318632, 702765, 1549997, 3418626, 7540017, 16630031, 36678688, 80897393, 178424817, 393528322, 867954037, 1914332891, 4222194104, 9312342245 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) counts permutations of length n which embed into the (infinite) increasing oscillating sequence given by 4,1,6,3,8,5,...,2k+2,2k-1,...; these are also the permutations which avoid {321, 2341, 3412, 4123}. - Vincent Vatter, May 23 2008

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

a(n) is the number of possible tilings of a 2 X n board, using dominos and L-shaped trominos. - Michael Tulskikh, Aug 21 2019

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

R. Brignall, N. Ruskuc and V. Vatter, Simple permutations: decidability and unavoidable substructures, Theoretical Computer Science 391 (2008), 150-163.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1053

D. Oudrar, Sur l'énumération de structures discrètes, une approche par la théorie des relations, Thesis (in French), arXiv:1604.05839 [math.CO], 2016.

D. Oudrar, M. Pouzet, Profile and hereditary classes of ordered relational structures, arXiv preprint arXiv:1409.1108 [math.CO], 2014 [The first version of this document erroneously gives the A-number as A005298]

V. Vatter, Small permutation classes, arXiv:0712.4006 [math.CO], 2007-2016.

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

FORMULA

Recurrence: a(0)=1, a(1)=1, a(2)=2; thereafter a(n) = 2*a(n-1)+a(n-3).

Sum(1/59*(4+3*_alpha^2+17*_alpha)*_alpha^(-1-n), _alpha = RootOf(-1+2*_Z+_Z^3)).

a(n) = A008998(n) - A008998(n-1). - R. J. Mathar, Feb 04 2014

Let u1 = 2.20556943... denote the real root of x^3-2*x^2-1. There is an explicit constant c1 = 0.460719842... such that for n>0, a(n) = nearest integer to c1*u1^n. - N. J. A. Sloane, Nov 07 2016

a(2n) = a(n)^2 - a(n-1)^2 + (1/2)*(a(n+2) - a(n+1) - a(n))^2. - Greg Dresden and Michael Tulskikh, Aug 20 2019

a(n) = 2^(n-1) + Sum_{i=3..n}(2^(n-i)*a(i-3)). - Greg Dresden, Aug 27 2019

MAPLE

spec := [S, {S=Sequence(Prod(Union(Prod(Z, Z, Z), Z), Sequence(Z)))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);

MATHEMATICA

CoefficientList[Series[(1 - x)/(1 - 2 x - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Feb 05 2014 *)

PROG

(PARI) Vec((1-x)/(1-2*x-x^3)+O(x^99)) \\ Charles R Greathouse IV, Nov 20 2011

(MAGMA) I:=[1, 1, 2]; [n le 3 select I[n] else 2*Self(n-1)+Self(n-3): n in [1..40]]

CROSSREFS

See A110513 for another version.

Column k=2 of A219987.

Sequence in context: A286945 A111297 A077864 * A190512 A110513 A018115

Adjacent sequences:  A052977 A052978 A052979 * A052981 A052982 A052983

KEYWORD

easy,nonn

AUTHOR

encyclopedia(AT)pommard.inria.fr, Jan 25 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 16 03:14 EST 2019. Contains 330013 sequences. (Running on oeis4.)