A328441 Number of inversion sequences of length n avoiding the consecutive pattern 100.

1, 1, 2, 6, 23, 109, 618, 4098, 31173, 267809, 2565520, 27120007, 313616532, 3938508241, 53381045786, 776672993274, 12074274033482, 199746500391688, 3503656507826887, 64951437702821877, 1268898555348831913, 26055882443142671038, 561050228044941209930, 12641053014560238560492, 297439800300471548183778

Offset: 0

Author

Juan S. Auli, Oct 17 2019

Keywords

• nonn

Comments

A length n inversion sequence e_1, e_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 100.

The term a(n) also 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) also counts the inversion sequences of length n avoiding the consecutive pattern 110, see the Auli and Elizalde links.

Examples

			Note that a(4)=23. Indeed, of the 24 inversion sequences of length 4, the only one that does not avoid the consecutive pattern 100 is 0100.
Similarly, 0110 is the only inversion sequence of length 4 that does not avoid the consecutive pattern 110.
		

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.
• Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.

Crossrefs

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

Programs

Maple

# after Alois P. Heinz in A328357
b := proc(n, x, t) local i; 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

i100[1] = 1; i100[2] = 2; i100[n_] := i100[n] = Sum[s100[n, k], {k, 0, n - 1}]; s100[n_, k_] := s100[n, k] = i100[n - 1] - Sum[s100[n - 2, j], {j, k + 1, n - 3}]; Flatten[{1, Table[i100[m], {m, 1, 25}]}] (* Vaclav Kotesovec, Oct 18 2019 *)

Formula

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