A328440 Number of inversion sequences of length n avoiding the consecutive patterns 000 and 100.

1, 1, 2, 5, 18, 81, 448, 2920, 21955, 186981, 1779170, 18706222, 215364181, 2694650157, 36408144034, 528302958022, 8193953571315, 135277259197031, 2368556730208679, 43838335667451773, 855200666797199814, 17538187897491897945, 377199969925672569364, 8489656058119117230574

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}. This is the same as the set of inversion sequences of length n avoiding the consecutive patterns 000 and 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}. This is the same as the set of inversion sequences of length n avoiding the consecutive patterns 000 and 110, see the Auli and Elizalde reference.

Links

Table of n, a(n) for n=0..23.

Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences II: avoiding patterns of relations, arXiv:1906.07365 [math.CO], 2019.

Example

The a(4)=18 length 4 inversion sequences avoiding the consecutive patterns 000 and 100 are 0010, 0110, 0020, 0120, 0101, 0011, 0021, 0121, 0102, 0012, 0112, 0022, 0122, 0103, 0013, 0113, 0023, and 0123.

Maple

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

b[n_, x_, t_] := b[n, x, t] = If[n == 0, 1, Sum[If[t && x <= i, 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 *)

Crossrefs

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

Sequence in context: A286282 A192637 A111916 * A308634 A118187 A307773

Adjacent sequences: A328437 A328438 A328439 * A328441 A328442 A328443

Keyword

nonn

Author

Juan S. Auli, Oct 17 2019

Status

approved