cp's OEIS Frontend

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

%I A215928 #96 Feb 19 2025 05:44:43
%S A215928 1,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,195025,
%T A215928 470832,1136689,2744210,6625109,15994428,38613965,93222358,225058681,
%U A215928 543339720,1311738121,3166815962,7645370045,18457556052,44560482149,107578520350,259717522849
%N A215928 a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.
%C A215928 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).
%C A215928 Row sums of triangle A155161. - _Philippe Deléham_, Aug 31 2012
%C A215928 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
%C A215928 For n > 0, A001333(n)/a(n) = A001333(n)/A000129(n), which converges to sqrt(2). - _Karl V. Keller, Jr._, May 17 2015
%H A215928 Karl V. Keller, Jr., <a href="/A215928/b215928.txt">Table of n, a(n) for n = 0..500</a>
%H A215928 Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1809.00742">Exhaustive generation for permutations avoiding a (colored) regular sets of patterns</a>, arXiv:1809.00742 [cs.DM], 2018.
%H A215928 E. S. Egge and T. Mansour, <a href="https://arxiv.org/abs/math/0205206">132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers, and Pell Numbers</a>, arXiv:math/0205206 [math.CO], 2002.
%H A215928 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,1).
%F A215928 a(n) = 2*a(n-1) + a(n-2) for n > 2, a(0) = a(1) = 1, a(2) = 2.
%F A215928 G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) = (1 - x - x^2) / (1 - 2*x - x^2).
%F A215928 a(n) = A000129(n) unless n = 0.
%F A215928 a(n+1) - a(n) = A078057(n-1).
%F A215928 PSUM transform is A024537.
%F A215928 PSUMSIGN transform is A097075.
%F A215928 INVERT transform of A000045(n). [Corrected by _Wolfdieter Lang_, Dec 07 2020]
%F A215928 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
%F A215928 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
%F A215928 a(n) = A069306(n-1) if n > 1. - _Michael Somos_, Oct 23 2018
%F A215928 E.g.f.: 1 + exp(x)*sinh(sqrt(2)*x)/sqrt(2). - _Franck Maminirina Ramaharo_, Nov 29 2018
%e A215928 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 + ...
%p A215928 f:= gfun:-rectoproc({a(n)=2*a(n-1)+a(n-2), a(0)=1, a(1)=1, a(2)=2}, a(n), remember):
%p A215928 map(f, [$0..100]); # _Robert Israel_, May 29 2015
%t A215928 CoefficientList[Series[(1 - x - x^2)/(1 - 2 x - x^2), {x, 0, 30}], x] (* _Vincenzo Librandi_, May 14 2015 *)
%o A215928 (PARI) {a(n) = if( n<0, 0, polcoeff( 1 / (1 - x / (1 - x / (1 - x / (1 + x)))) + x * O(x^n), n))};
%o A215928 (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
%Y A215928 Cf. A000129, A000045, A024537, A069306, A078057, A097075, A142474.
%K A215928 nonn,easy
%O A215928 0,3
%A A215928 _Michael Somos_, Aug 27 2012