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

%I #25 Mar 01 2020 04:23:53

%S 1,1,2,4,10,30,100,376,1566,7094,34751,182841,1026167,6112799,

%T 38489481,255204077,1776046697,12936265145,98368170749,779127467795,

%U 6414876317675,54802126603135,484967246285755,4438877330941077,41963817964950737,409224941931240185

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

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

%H Alois P. Heinz, <a href="/A328358/b328358.txt">Table of n, a(n) for n = 0..578</a>

%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 The length 4 inversion sequences avoiding the consecutive patterns 012, 021, 010, 120 are 0000, 0110, 0001, 0011, 0111, 0002, 0112, 0022, 0003, 0113.

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

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

%p end:

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

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Oct 14 2019

%t 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}]];

%t a[n_] := b[n, 0, False, 2];

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

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

%K nonn

%O 0,3

%A _Juan S. Auli_, Oct 13 2019

%E a(11)-a(25) from _Alois P. Heinz_, Oct 14 2019