login
A279560
Number of length n inversion sequences avoiding the patterns 100, 210, 201, and 102.
23
1, 1, 2, 6, 21, 76, 277, 1016, 3756, 13998, 52554, 198568, 754316, 2878552, 11027384, 42384412, 163372325, 631290168, 2444700421, 9485463044, 36866810877, 143508889270, 559399074443, 2183269032876, 8530724152279, 33366805383326, 130633854520329, 511889287682280
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
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
KEYWORD
nonn
AUTHOR
Megan A. Martinez, Jan 17 2017
EXTENSIONS
More terms from Michel Marcus, Jan 18 2017
STATUS
approved