A110513 -id:A110513 - cp's OEIS frontend

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

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, 20539017381, 45300228866

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

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 dominoes and L-shaped trominoes. - Michael Tulskikh, Aug 21 2019
a(n) = A190512(n-1) for n>0. - Greg Dresden, Feb 28 2020

Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 4.
Robert Brignall, Nik Ruškuc, and Vincent Vatter, Simple permutations: decidability and unavoidable substructures, Theoretical Computer Science 391 (2008), 150-163.
Greg Dresden and Michael Tulskikh, Tilings of 2 X n boards with dominos and L-shaped trominos, Washington & Lee University (2021).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1053
Djamila 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.
Djamila Oudrar and Maurice 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]
Vincent Vatter, Small permutation classes, arXiv:0712.4006 [math.CO], 2007-2016.
Index entries for linear recurrences with constant coefficients, signature (2,0,1).

See A190512 and A110513 for other versions of this sequence.
Column k=2 of A219987.
Cf. A008998.

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

R:=PowerSeriesRing(Integers(), 32); Coefficients(R!( (1 - x)/(1 - 2*x - x^3))); // Marius A. Burtea, Feb 14 2020

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

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

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

Recurrence: a(0)=1, a(1)=1, a(2)=2; thereafter a(n) = 2*a(n-1)+a(n-3).
a(n) = 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
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
a(n) = A008998(n-1) + A008998(n-3). - Michael Tulskikh, Feb 14 2020

A110511 Riordan array (1/(1+x), x(1-x)/(1+x)^2).

Original entry on oeis.org

1, -1, 1, 1, -4, 1, -1, 9, -7, 1, 1, -16, 26, -10, 1, -1, 25, -70, 52, -13, 1, 1, -36, 155, -190, 87, -16, 1, -1, 49, -301, 553, -403, 131, -19, 1, 1, -64, 532, -1372, 1462, -736, 184, -22, 1, -1, 81, -876, 3024, -4446, 3206, -1216, 246, -25, 1, 1, -100, 1365, -6084, 11826, -11584, 6190, -1870, 317, -28, 1, -1, 121, -2035

Offset: 0

Paul Barry, Jul 24 2005

Inverse of number triangle A110506. Row sums are A110512. Diagonal sums are A110513. Product of (1/(1+x), x/(1+x)) (inverse binomial transform matrix) and (1, x(1-2x)) (A110509).

			Rows begin
   1;
  -1,   1;
   1,  -4,   1;
  -1,   9,  -7,   1;
   1, -16,  26, -10,   1;
  -1,  25, -70,  52, -13,   1;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

T[n_, k_] := Sum[(-1)^(n - j)*Binomial[n, j]*(-2)^(j - k)*Binomial[k, j - k], {j, 0, n}]; Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* G. C. Greubel, Aug 29 2017 *)

for(n=0,20, for(k=0,n, print1(sum(j=0,n, (-1)^(n-j)*binomial(n, j)*(-2)^(j-k)*binomial(k, j-k)), ", "))) \\ G. C. Greubel, Aug 29 2017

Number triangle: T(n, k) = Sum_{j=0..n} (-1)^(n-j)*C(n, j)*(-2)^(j-k)*C(k, j-k).
T(n, k) = Sum_{j=0..n} Sum_{i=0..k} C(k, i)*C(n+k-i-j-1, n-k-i-j)*(-1)^(n-k).
T(n,k) = T(n-1,k-1) - 2*T(n-1,k) - T(n-2,k) - T(n-2,k-1), T(0,0)=1, T(1,0)=-1, T(1,1)=1, T(n,k)=0 if k < 0 or if k > n. - Philippe Deléham, Jan 12 2014

A190512 Number of one-sided n-step prudent walks, avoiding single west step only, i.e., two or more consecutive west steps are permitted.

Original entry on oeis.org

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, 20539017381, 45300228866

Offset: 0

Shanzhen Gao, May 11 2011

			a(2)=5 since there are 5 such walks: WW, NN, EN, NE, EE.

S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (2,0,1).

Cf. A110513 (essentially a signed version).

Cf. A052980 (essentially the same sequence).

my(x='x+O('x^35)); Vec((1+x^2)/(1-2*x-x^3)) \\ Michel Marcus, Jun 28 2021

a(n) = A052980(n+1). - R. J. Mathar, May 16 2011

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Formula

A110511 Riordan array (1/(1+x), x(1-x)/(1+x)^2).

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

A190512 Number of one-sided n-step prudent walks, avoiding single west step only, i.e., two or more consecutive west steps are permitted.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula