A328434 - OEIS

%I #15 Jun 01 2022 01:55:38

%S 1,1,2,6,21,81,346,1630,8350,45958,269815,1681285,11071336,76743040,

%T 558062437,4244853573,33687390663,278296576327,2388351295760,

%U 21254019548162,195801111412320,1864508416302520,18326903140310011,185711672802101781,1937795878138303715

%N Number of inversion sequences of length n avoiding the consecutive patterns 101, 102, 201, and 210.

%C 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}. This is the same as the set of inversion sequences of length n avoiding the consecutive patterns 101, 102, 201, and 210.

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

%e Note that a(4)=21. Indeed, of the 24 inversion sequences of length 4, the only ones that do not avoid the consecutive patterns 101, 102, 201, and 210 are 0101, 0102 and 0103.

%p # after _Alois P. Heinz_ in A328357

%p b := proc(n, x, t) option remember; `if`(n=0, 1, add(

%p        `if`(t and i>x, 0, b(n-1, i, i<>x and x>-1)), i=0..n-1))

%p      end proc:

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

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

%t b[n_, x_, t_] := b[n, x, t] = If[n == 0, 1, Sum[If[t && i > x, 0, b[n - 1, i, i != x && x > -1]], {i, 0, n - 1}]];

%t a[n_] := b[n, -1, False];

%t a /@ Range[0, 24] (* _Jean-François Alcover_, Mar 02 2020 after _Alois P. Heinz_ in A328357 *)

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

%K nonn

%O 0,3

%A _Juan S. Auli_, Oct 16 2019