|
|
A328357
|
|
Number of inversion sequences of length n avoiding the consecutive patterns 000, 001, 011, 012.
|
|
21
|
|
|
1, 1, 2, 1, 4, 6, 36, 117, 804, 4266, 33768, 249144, 2289348, 21353472, 227212824, 2533824900, 30914509212, 398623158096, 5508014798052, 80377645583430, 1242697826967816, 20218588415853480, 346035438765576720, 6206862951272939550, 116518581654518098332
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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}. Alternatively, we can describe this as the set of inversion sequences of length n avoiding the consecutive patterns 000, 001, 011, 012.
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ n! * c * (3^(3/2)/(2*Pi))^n / n^(2*Pi/3^(3/2)), where c = 0.75844492121718325018323312623016463... - Vaclav Kotesovec, Oct 17 2019
|
|
EXAMPLE
|
The a(4)=4 length 4 inversion sequences avoiding the consecutive patterns 000, 001, 011, 012 are 0100, 0101, 0102, 0103.
The a(5)=6 length 5 inversion sequences are 01010, 01020, 01021, 01030, 01031, 01032.
|
|
MAPLE
|
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=1..n))
end:
a:= n-> b(n, 0, false):
|
|
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, 1, n}]];
a[n_] := b[n, 0, False];
|
|
CROSSREFS
|
Cf. A328358, A328429, A328430, A328431, A328432, A328433, A328434, A328435, A328436, A328437, A328438, A328439, A328440, A328441, A328442.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|