login
A328440
Number of inversion sequences of length n avoiding the consecutive patterns 000 and 100.
15
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
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
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 *)
KEYWORD
nonn
AUTHOR
Juan S. Auli, Oct 17 2019
STATUS
approved