login
A328357
Number of inversion sequences of length n avoiding the consecutive patterns 000, 001, 011, 012.
21
1, 1, 2, 1, 4, 6, 36, 117, 804, 4266, 33768, 249144, 2289348, 21353472, 227212824, 2533824900, 30914509212, 398623158096, 5508014798052, 80377645583430, 1242697826967816, 20218588415853480, 346035438765576720, 6206862951272939550, 116518581654518098332
OFFSET
0,3
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers such that 0 <= e_i < i. The term a(n) counts the inversion sequences of length n with no entries e_i, e_{i+1}, e_{i+2} such that e_i <= e_{i+1} <= e_{i+2}. Alternatively, we can describe this as the set of inversion sequences of length n avoiding the consecutive patterns 000, 001, 011, 012.
LINKS
Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences II: avoiding patterns of relations, arXiv:1906.07365 [math.CO], 2019.
FORMULA
a(n) ~ n! * c * (3^(3/2)/(2*Pi))^n / n^(2*Pi/3^(3/2)), where c = 0.75844492121718325018323312623016463... - Vaclav Kotesovec, Oct 17 2019
EXAMPLE
The a(4)=4 length 4 inversion sequences avoiding the consecutive patterns 000, 001, 011, 012 are 0100, 0101, 0102, 0103.
The a(5)=6 length 5 inversion sequences are 01010, 01020, 01021, 01030, 01031, 01032.
MAPLE
b:= proc(n, x, t) option remember; `if`(n=0, 1, add(
`if`(t and i<=x, 0, b(n-1, i, i<=x)), i=1..n))
end:
a:= n-> b(n, 0, false):
seq(a(n), n=0..24); # Alois P. Heinz, Oct 14 2019
MATHEMATICA
b[n_, x_, t_] := b[n, x, t] = If[n == 0, 1, Sum[If[t && i <= x, 0, b[n - 1, i, i <= x]], {i, 1, n}]];
a[n_] := b[n, 0, False];
a /@ Range[0, 24] (* Jean-François Alcover, Feb 25 2020, after Alois P. Heinz *)
KEYWORD
nonn
AUTHOR
Juan S. Auli, Oct 13 2019
EXTENSIONS
Terms a(11)..a(16) from Joerg Arndt, Oct 14 2019
a(17)-a(24) from Alois P. Heinz, Oct 14 2019
STATUS
approved