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

Author

Michel Marcus, Oct 26 2015

Keywords

• nonn

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.
• Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See p. 2.

Crossrefs

Cf. A263778, A263779, A263780.

Programs

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 *)

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

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

Extensions

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

More terms from Lars Blomberg, Jan 18 2017