A328441 - OEIS

%I #21 Aug 21 2020 17:33:21

%S 1,1,2,6,23,109,618,4098,31173,267809,2565520,27120007,313616532,

%T 3938508241,53381045786,776672993274,12074274033482,199746500391688,

%U 3503656507826887,64951437702821877,1268898555348831913,26055882443142671038,561050228044941209930,12641053014560238560492,297439800300471548183778

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

%C 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.

%C 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.

%H Vaclav Kotesovec, <a href="/A328441/b328441.txt">Table of n, a(n) for n = 0..448</a>

%H Juan S. Auli, <a href="https://search.proquest.com/openview/3f0cef1fbdb016d61e16412e4b855969/1">Pattern Avoidance in Inversion Sequences</a>, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/1904.02694">Consecutive Patterns in Inversion Sequences</a>, arXiv:1904.02694 [math.CO], 2019.

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/1906.07365">Consecutive patterns in inversion sequences II: avoiding patterns of relations</a>, arXiv:1906.07365 [math.CO], 2019.

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/2003.11533">Wilf equivalences between vincular patterns in inversion sequences</a>, arXiv:2003.11533 [math.CO], 2020.

%F a(n) ~ n! * c / sqrt(n), where c = 2.428754692682297906864850201408427747198... - _Vaclav Kotesovec_, Oct 18 2019

%e 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.

%e Similarly, 0110 is the only inversion sequence of length 4 that does not avoid the consecutive pattern 110.

%p # after _Alois P. Heinz_ in A328357

%p 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;

%p a := n -> b(n, -1, false);

%p seq(a(n), n = 0 .. 24);

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

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

%K nonn

%O 0,3

%A _Juan S. Auli_, Oct 17 2019