cp's OEIS Frontend

A052980 Expansion of (1 - x)/(1 - 2*x - x^3).

%I A052980 #120 May 28 2025 14:18:51
%S A052980 1,1,2,5,11,24,53,117,258,569,1255,2768,6105,13465,29698,65501,144467,
%T A052980 318632,702765,1549997,3418626,7540017,16630031,36678688,80897393,
%U A052980 178424817,393528322,867954037,1914332891,4222194104,9312342245,20539017381,45300228866
%N A052980 Expansion of (1 - x)/(1 - 2*x - x^3).
%C A052980 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
%C A052980 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
%C A052980 a(n) is the number of possible tilings of a 2 X n board, using dominoes and L-shaped trominoes. - _Michael Tulskikh_, Aug 21 2019
%C A052980 a(n) = A190512(n-1) for n>0. - _Greg Dresden_, Feb 28 2020
%D A052980 Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
%H A052980 Vincenzo Librandi, <a href="/A052980/b052980.txt">Table of n, a(n) for n = 0..1000</a>
%H A052980 Kassie Archer and Noel Bourne, <a href="https://arxiv.org/abs/2505.05218">Pattern avoidance in compositions and powers of permutations</a>, arXiv:2505.05218 [math.CO], 2025. See p. 4.
%H A052980 Robert Brignall, Nik Ruškuc, and Vincent Vatter, <a href="http://dx.doi.org/10.1016/j.tcs.2007.10.037">Simple permutations: decidability and unavoidable substructures</a>, Theoretical Computer Science 391 (2008), 150-163.
%H A052980 Greg Dresden and Michael Tulskikh, <a href="https://dresden.academic.wlu.edu/files/2021/01/TwoByNWeb.pdf">Tilings of 2 X n boards with dominos and L-shaped trominos</a>, Washington & Lee University (2021).
%H A052980 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1053">Encyclopedia of Combinatorial Structures 1053</a>
%H A052980 Djamila Oudrar, <a href="http://arxiv.org/abs/1604.05839">Sur l'énumération de structures discrètes, une approche par la théorie des relations</a>, Thesis (in French), arXiv:1604.05839 [math.CO], 2016.
%H A052980 Djamila Oudrar and Maurice Pouzet, <a href="http://arxiv.org/abs/1409.1108">Profile and hereditary classes of ordered relational structures</a>, arXiv preprint arXiv:1409.1108 [math.CO], 2014 [The first version of this document erroneously gives the A-number as A005298]
%H A052980 Vincent Vatter, <a href="http://arXiv.org/abs/0712.4006">Small permutation classes</a>, arXiv:0712.4006 [math.CO], 2007-2016.
%H A052980 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,1).
%F A052980 Recurrence: a(0)=1, a(1)=1, a(2)=2; thereafter a(n) = 2*a(n-1)+a(n-3).
%F A052980 a(n) = Sum(1/59*(4+3*_alpha^2+17*_alpha)*_alpha^(-1-n), _alpha = RootOf(-1+2*_Z+_Z^3)).
%F A052980 a(n) = A008998(n) - A008998(n-1). - _R. J. Mathar_, Feb 04 2014
%F A052980 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
%F A052980 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
%F A052980 a(n) = 2^(n-1) + Sum_{i=3..n}(2^(n-i)*a(i-3)). - _Greg Dresden_, Aug 27 2019
%F A052980 a(n+1) = (Sum_{i >= 0} 2^(n-3i-2)*(4*binomial(n-2i, i) + binomial(n-2i-2, i))). - _Michael Tulskikh_, Feb 14 2020
%F A052980 a(n) = A008998(n-1) + A008998(n-3). - _Michael Tulskikh_, Feb 14 2020
%p A052980 spec := [S,{S=Sequence(Prod(Union(Prod(Z,Z,Z),Z),Sequence(Z)))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
%t A052980 CoefficientList[Series[(1 - x)/(1 - 2 x - x^3), {x, 0, 40}], x] (* _Vincenzo Librandi_, Feb 05 2014 *)
%o A052980 (PARI) Vec((1-x)/(1-2*x-x^3)+O(x^99)) \\ _Charles R Greathouse IV_, Nov 20 2011
%o A052980 (Magma) I:=[1,1,2]; [n le 3 select I[n] else 2*Self(n-1)+Self(n-3): n in [1..40]];
%o A052980 (Magma) R<x>:=PowerSeriesRing(Integers(), 32); Coefficients(R!( (1 - x)/(1 - 2*x - x^3))); // _Marius A. Burtea_, Feb 14 2020
%Y A052980 See A190512 and A110513 for other versions of this sequence.
%Y A052980 Column k=2 of A219987.
%Y A052980 Cf. A008998.
%K A052980 easy,nonn
%O A052980 0,3
%A A052980 encyclopedia(AT)pommard.inria.fr, Jan 25 2000