|
|
A263777
|
|
Number of inversion sequences avoiding pattern 201 (or 210).
|
|
32
|
|
|
1, 1, 2, 6, 24, 118, 674, 4306, 29990, 223668, 1763468, 14558588, 124938648, 1108243002, 10115202962, 94652608690, 905339525594, 8829466579404, 87618933380020, 883153699606024, 9028070631668540, 93478132393544988, 979246950529815364, 10368459385853924212
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
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).
|
|
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}];
|
|
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;
};
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|