A328358 Number of inversion sequences of length n avoiding the consecutive patterns 012, 021, 010, 120.

1, 1, 2, 4, 10, 30, 100, 376, 1566, 7094, 34751, 182841, 1026167, 6112799, 38489481, 255204077, 1776046697, 12936265145, 98368170749, 779127467795, 6414876317675, 54802126603135, 484967246285755, 4438877330941077, 41963817964950737, 409224941931240185

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, 021, 010, 120.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..578

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

Example

The length 4 inversion sequences avoiding the consecutive patterns 012, 021, 010, 120 are 0000, 0110, 0001, 0011, 0111, 0002, 0112, 0022, 0003, 0113.

Maple

b:= proc(n, x, t, c) option remember; `if`(n=0, 1, add(`if`(i<x
      and t and c=0, 0, b(n-1, i, i<>x, max(0, c-1))), i=1..n))
    end:
a:= n-> b(n, 0, false, 2):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 14 2019

Mathematica

b[n_, x_, t_, c_] := b[n, x, t, c] = If[n == 0, 1, Sum[If[i < x && t && c == 0, 0, b[n - 1, i, i != x, Max[0, c - 1]]], {i, 1, n}]];
a[n_] := b[n, 0, False, 2];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 01 2020, after Alois P. Heinz *)

Crossrefs

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

Sequence in context: A372018 A360814 A337488 * A007558 A094957 A000733

Adjacent sequences: A328355 A328356 A328357 * A328359 A328360 A328361

Keyword

nonn

Author

Juan S. Auli, Oct 13 2019

Extensions

a(11)-a(25) from Alois P. Heinz, Oct 14 2019

Status

approved