OFFSET
0,3
COMMENTS
A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i<j<k) such that e_i > e_j <> e_k and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 102, 201, and 210.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1664
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
FORMULA
a(n) ~ 4^n / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 07 2021
EXAMPLE
The length 4 inversion sequences avoiding (102, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<4, n!,
((2*(12*n^3-91*n^2+213*n-149))*a(n-1)
-(3*(21*n^3-162*n^2+392*n-291))*a(n-2)
+(2*(33*n^3-257*n^2+633*n-484))*a(n-3)
-(4*(2*n-7))*(3*n^2-13*n+13)*a(n-4))
/ ((n-1)*(3*n^2-19*n+29)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Feb 22 2017
MATHEMATICA
a[n_] := a[n] = If[n < 4, n!, ((2*(12*n^3 - 91*n^2 + 213*n - 149))*a[n-1] - (3*(21*n^3 - 162*n^2 + 392*n - 291))*a[n-2] + (2*(33*n^3 - 257*n^2 + 633*n - 484))*a[n-3] - (4*(2*n - 7))*(3*n^2 - 13*n + 13)*a[n-4]) / ((n - 1)*(3*n^2 - 19*n + 29))]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Megan A. Martinez, Feb 09 2017
EXTENSIONS
a(10)-a(26) from Alois P. Heinz, Feb 22 2017
STATUS
approved