A263777 Number of inversion sequences avoiding pattern 201 (or 210).

1, 1, 2, 6, 24, 118, 674, 4306, 29990, 223668, 1763468, 14558588, 124938648, 1108243002, 10115202962, 94652608690, 905339525594, 8829466579404, 87618933380020, 883153699606024, 9028070631668540, 93478132393544988, 979246950529815364, 10368459385853924212

Offset

0,3

Links

Lars Blomberg and Gheorghe Coserea, Table of n, a(n) for n = 0..777, terms 1..100 from Lars Blomberg.

Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.

Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015. See equations (4,5).

Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Jay Pantone, The enumeration of inversion sequences avoiding the patterns 201 and 210, arXiv:2310.19632 [math.CO], 2023.

Formula

a(n) = Sum_{k=0..n-1} Sum_{p=-1,k-1} T(n,k,p), where T(n,k,p) = Sum_{i=-1..p} T(n-1,k,i) + Sum_{j=p+1..k} T(n-1,j,p) with initial conditions T(n,k,p) = 0 if k >= n and T(n,k,-1) = (n-k)/n * binomial(n-1+k,k). (eqn. (4) and (5) in Corteel link) - Gheorghe Coserea, Sep 21 2017

a(n) ~ c * (27/2)^n / n^alfa, where alfa = 5.7667921227... and c = 9.973... - Vaclav Kotesovec, Oct 16 2021

Mathematica

T[n_, k_, _] /; k >= n = 0; T[n_, k_, -1] := (n-k)/n*Binomial[n+k-1, k];
T[n_, k_, p_] := T[n, k, p] = Sum[T[n-1, k, i], {i, -1, p}] + Sum[T[n-1, j, p], {j, p+1, k}];
a[0] = 1; a[n_] := Sum[T[n, k, p], {k, 0, n-1}, {p, -1, k-1}];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Aug 10 2018 *)

Prog

(PARI)
seq(N) = {
  my(a=vector(N), t=vector(2, k, matrix(N, N)), s=matrix(N+1, N+1),
     C=(n, k)->(n-k)/n*binomial(n-1+k, k));
  for (n=1, N, for (k=1, n, for(p=1, k-1,
      s[k+1, p+1] = s[k+1, p] + t[1+n%2][k, p];
      s[p+1, k+1] = s[p+1, k] + t[1+n%2][k, p];
      t[1+(n+1)%2][k, p] = s[k+1, p+1] + s[p+1, k+1] + C(n-1, k-1)));
    a[n] = sum(k=1, n, sum(p=1, k-1, t[1+(n+1)%2][k, p])) + C(n+1, n));
  a;
};
concat(1, seq(23)) \\ Gheorghe Coserea, Nov 20 2017

Crossrefs

Cf. A263778, A263779, A263780.

Sequence in context: A079106 A247472 A224295 * A088713 A193938 A298432

Adjacent sequences: A263774 A263775 A263776 * A263778 A263779 A263780

Keyword

nonn

Author

Michel Marcus, Oct 26 2015

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 15 2016

More terms from Lars Blomberg, Jan 18 2017

Status

approved