A328437 Number of inversion sequences of length n avoiding the consecutive pattern 001.

1, 1, 2, 4, 11, 42, 210, 1292, 9352, 77505, 722294, 7470003, 84854788, 1049924370, 14052654158, 202271440732, 3115338658280, 51118336314648, 890201500701303, 16397264064993185, 318505677099378561, 6506565509515408206, 139449260758011488550, 3128599281190613701180

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}. That is, a(n) counts the inversion sequences of length n avoiding the consecutive pattern 001.

Examples

			The a(4)=11 length 4 inversion sequences avoiding the consecutive pattern 001 are 0000, 0100, 0110, 0120, 0101, 0111, 0121, 0102, 0122, 0103, and 0123.
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..448
• Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
• Juan S. Auli and Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019.
• 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, A328435, A328436, 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 i = x, 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 && i == x, 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 *)

Formula

a(n) ~ n! * c / sqrt(n), where c = 0.549342310436989831962783548104445992522... - Vaclav Kotesovec, Oct 18 2019