A328429 Number of inversion sequences of length n avoiding the consecutive patterns 012, 101, 102, and 201.

1, 1, 2, 5, 14, 46, 170, 691, 3073, 14809, 76666, 423886, 2490514, 15479614, 101389508, 697513653, 5025406212, 37819960947, 296618360520, 2419362514273, 20484053318220, 179723185666151, 1631519158000420, 15302546831928727, 148099068509673563

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 012, 101, 102, and 201.

Links

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

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)=14 length 4 inversion sequences avoiding the consecutive patterns 012, 101, 102, and 201 are 0000, 0100, 0010, 0110, 0020, 0001, 0011, 0111, 0021, 0002, 0112, 0022, 0003, and 0113.

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, A328430, A328431, A328432, A328433, A328434, A328435, A328436, A328437, A328438, A328439, A328440, A328441, A328442.

Sequence in context: A240617 A001680 A275424 * A107268 A231211 A006216

Adjacent sequences: A328426 A328427 A328428 * A328430 A328431 A328432

Keyword

nonn

Author

Juan S. Auli, Oct 15 2019

Status

approved