A328357 Number of inversion sequences of length n avoiding the consecutive patterns 000, 001, 011, 012.

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

Author

Juan S. Auli, Oct 13 2019

Keywords

• nonn

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.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..465
• Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences II: avoiding patterns of relations, arXiv:1906.07365 [math.CO], 2019.

Crossrefs

Cf. A328358, A328429, A328430, A328431, A328432, A328433, A328434, A328435, A328436, A328437, A328438, A328439, A328440, A328441, A328442.

Programs

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

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

Extensions

Terms a(11)..a(16) from Joerg Arndt, Oct 14 2019

a(17)-a(24) from Alois P. Heinz, Oct 14 2019