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 and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 100, 210, 201, and 102.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1665
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) = binomial(2n-2,n-1) + Sum_{k=2..n-2} Sum_{i=1..k-1} Sum_{u=1..i} Sum_{d=0..u-1} ((i-d+1)/(i+1)*binomial(i+d,d)) for n>0, a(0)=1.
a(n) ~ 4^(n-1) / sqrt(Pi*n). - Vaclav Kotesovec, Oct 07 2021
EXAMPLE
The length 4 inversion sequences avoiding (100, 210, 201, 102) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.
MAPLE
a:= proc(n) option remember; `if`(n<4, n!,
((6*(9*n^4-61*n^3+100*n^2+52*n-140))*a(n-1)
-(3*(3*n-8))*(9*n^3-38*n^2+3*n+70)*a(n-2)
+(2*(2*n-7))*(9*n^3-31*n^2-2*n+60)*a(n-3))
/ ((9*n^3-58*n^2+87*n+22)*n))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Feb 24 2017
MATHEMATICA
a[0] = 1; a[n_] := Binomial[2n-2, n-1] + Sum[(4i Binomial[2i+1, i+1]) / ((i+2)(i+3)), {k, 2, n-2}, {i, 1, k-1}]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017 *)
PROG
(PARI) a(n) = if (n==0, 1, binomial(2*n-2, n-1) + sum(k=2, n-2, sum(i=1, k-1, sum(u=1, i, sum(d=0, u-1, ((i-d+1)/(i+1)*binomial(i+d, d))))))); \\ Michel Marcus, Jan 18 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Megan A. Martinez, Jan 17 2017
EXTENSIONS
More terms from Michel Marcus, Jan 18 2017
STATUS
approved