A328435 Number of inversion sequences of length n avoiding the consecutive patterns 101, 102, and 201.

1, 1, 2, 6, 21, 83, 368, 1814, 9837, 58095, 370499, 2534374, 18493023, 143280489, 1173971656, 10136279104, 91936857611, 873547634921, 8673546319685, 89796095349193, 967384904147690, 10825116242427973, 125613702370667158, 1509222589338456874, 18748890945849736182

Offset: 0

Author

Juan S. Auli, Oct 17 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}. This is the same as the set of inversion sequences of length n avoiding the consecutive patterns 101, 102, and 201.

Examples

			Note that a(4)=21. Indeed, of the 24 inversion sequences of length 4, the only ones that do not avoid the consecutive patterns 101, 102, and 201 are 0101, 0102, and 0103.
		

Links

• Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences II: avoiding patterns of relations, arXiv:1906.07365 [math.CO], 2019.

Crossrefs

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

Programs

Maple

# after Alois P. Heinz in A328357
b := proc(n, x, t) option remember; `if`(n = 0, 1, add(
       `if`(t and x < i, 0, b(n - 1, i, i < x)), i = 0 .. n - 1))
     end proc:
a := n -> b(n, -1, false):
seq(a(n), n = 0 .. 24);

Mathematica

b[n_, x_, t_] := b[n, x, t] = If[n == 0, 1, Sum[If[t && x < i, 0, b[n - 1, i, i < x]], {i, 0, n - 1}]];
a[n_] := b[n, -1, False];
a /@ Range[0, 24] (* Jean-François Alcover, Mar 02 2020 after Alois P. Heinz in A328357 *)