A328436 Number of inversion sequences of length n avoiding the consecutive patterns 000 and 001.

1, 1, 2, 3, 9, 37, 190, 1181, 8564, 70914, 659810, 6811371, 77232836, 953969548, 12747856402, 183218649413, 2818050980941, 46182485773217, 803323102085452, 14781372445602234, 286838921699435184, 5854404018902152208, 125367868007259046305, 2810511319383912299122

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

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)=9 length 4 inversion sequences avoiding the consecutive patterns 000 and 001 are 0100, 0110, 0120, 0101, 0121, 0102, 0122, 0103, and 0123.

Maple

# after Alois P. Heinz in A328357
b := proc(n, x, t) option remember; `if`(n = 0, 1, add(
       `if`(t and i = x, 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 && i == x, 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, A328437, A328438, A328439, A328440, A328441, A328442.

Sequence in context: A306523 A095412 A074428 * A125052 A181139 A162093

Adjacent sequences: A328433 A328434 A328435 * A328437 A328438 A328439

Keyword

nonn

Author

Juan S. Auli, Oct 17 2019

Status

approved