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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215928 a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2. 4
1, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, 225058681, 543339720, 1311738121, 3166815962, 7645370045, 18457556052, 44560482149, 107578520350, 259717522849 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Pell numbers with a(0) replaced by 1. - R. J. Mathar, Sep 08 2012

Number of 132-avoiding two-stack sortable permutations. See Theorem 2.2 of Egge and Mansour which gives a generating function equation P(x) = 1 + x + 2*x^2 + x*(P(x) - 1 - x) + x^2*(P(x) - 1) + x*(P(x) - 1 - x).

Row sums of triangle A155161. - Philippe Deléham, Aug 31 2012

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

For n > 0, A001333(n)/a(n) = A001333(n)/A000129(n), which converges to sqrt(2). - Karl V. Keller, Jr., May 17 2015

LINKS

Karl V. Keller, Jr., Table of n, a(n) for n = 0..500

Phan Thuan Do, Thi Thu Huong Tran, Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.

E. S. Egge and T. Mansour, 132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers, and Pell Numbers, arXiv:math/0205206 [math.CO], 2002.

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

FORMULA

a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.

G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) = (1 - x - x^2) / (1 - 2*x - x^2).

a(n) = A000129(n) unless n = 0.

a(n+1) - a(n) = A078057(n-1).

PSUM transform is A024537.

PSUMSIGN transform is A097075.

INVERT transform of A142474.

G.f.: 1/( 1 - (Sum_{k>=0} x*(x + x^2)^k) ) = 1/( 1 - (Sum_{k>=1} x/(1 - x^2))^k) ). - Joerg Arndt, Sep 30 2012

a(n) = 1/2*((1 + sqrt(2))^(n - 1) + (1 - sqrt(2))^(n - 1)) + 1/4*sqrt(2)*((1 + sqrt(2))^(n - 1) - (1 - sqrt(2))^(n - 1)), for n > 0. - Paolo P. Lava, Oct 26 2012

G.f.: 1 + Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 + x)/( x*(4*k + 4 + x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 06 2013

a(n) = A069306(n-1) if n > 1. - Michael Somos, Oct 23 2018

E.g.f.: 1 + exp(x)*sinh(sqrt(2)*x)/sqrt(2). - Franck Maminirina Ramaharo, Nov 29 2018

EXAMPLE

G.f. = 1 + x + 2*x^2 + 5*x^3 + 12*x^4 + 29*x^5 + 70*x^6 + 169*x^7 + 408*x^8 + 985*x^9 + ...

MAPLE

f:= gfun:-rectoproc({a(n)=2*a(n-1)+a(n-2), a(0)=1, a(1)=1, a(2)=2}, a(n), remember):

map(f, [$0..100]); # Robert Israel, May 29 2015

MATHEMATICA

CoefficientList[Series[(1 - x - x^2)/(1 - 2 x - x^2), {x, 0, 30}], x] (* Vincenzo Librandi, May 14 2015 *)

PROG

(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) + x * O(x^n), n))};

(MAGMA) [1] cat [ n le 2 select (n) else 2*Self(n-1)+Self(n-2): n in [1..35] ]; // Vincenzo Librandi, May 14 2015

CROSSREFS

Cf. A000129, A024537, A069306, A078057, A097075, A142474.

Sequence in context: A215936 A000129 A077985 * A054198 A054196 A131710

Adjacent sequences:  A215925 A215926 A215927 * A215929 A215930 A215931

KEYWORD

nonn,easy

AUTHOR

Michael Somos, Aug 27 2012

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 November 18 02:07 EST 2019. Contains 329242 sequences. (Running on oeis4.)