login
A328437
Number of inversion sequences of length n avoiding the consecutive pattern 001.
16
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,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}. That is, a(n) counts the inversion sequences of length n avoiding the consecutive pattern 001.
LINKS
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.
FORMULA
a(n) ~ n! * c / sqrt(n), where c = 0.549342310436989831962783548104445992522... - Vaclav Kotesovec, Oct 18 2019
EXAMPLE
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.
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 = 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 *)
KEYWORD
nonn
AUTHOR
Juan S. Auli, Oct 17 2019
STATUS
approved