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,3

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.

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.

Formula

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

Example

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.

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

Crossrefs

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

Sequence in context: A093345 A289681 A002136 * A328507 A208733 A264899

Adjacent sequences: A328438 A328439 A328440 * A328442 A328443 A328444

Keyword

nonn

Author

Juan S. Auli, Oct 17 2019

Status

approved