|
%I #39 Feb 21 2020 07:37:07
%S 1,1,2,6,20,68,233,805,2807,9879,35073,125513,452389,1641029,5986994,
%T 21954974,80884424,299233544,1111219334,4140813374,15478839554,
%U 58028869154,218123355524,821908275548,3104046382352,11747506651600,44546351423300,169227201341652
%N Number of length n inversion sequences avoiding the patterns 110, 120, and 021.
%C 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 110, 120, and 021.
%H Alois P. Heinz, <a href="/A279557/b279557.txt">Table of n, a(n) for n = 0..1668</a>
%H Megan A. Martinez, Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.
%F a(n) = 1 + Sum_{t=1..n-1} Sum_{k=t+2..n+1} (k-t-1)*(k-t)/(n-t+1) * binomial(2n-k-t+1,n-k+1).
%F Conjecture: a(n) = C_{n+1}-Sum_{i=1..n} C_i where C_i is the i-th Catalan number, binomial(2i,i)/(i+1).
%F Assuming the conjecture a(n) ~ (64/3)*4^n/((4*n+7)^(3/2)*sqrt(Pi)). - _Peter Luschny_, Feb 24 2017
%F From _Alois P. Heinz_, Mar 11 2017: (Start)
%F a(n) = 1 + A114277(n-2) for n>1.
%F G.f.: (sqrt(1-4*x)+2*x-1)*(2*x-1)/(2*(1-x)*x^2). (End)
%F D-finite with recurrence: (n+2)*a(n) +(-7*n-4)*a(n-1) +2*(7*n-5)*a(n-2) +4*(-2*n+3)*a(n-3)=0. - _R. J. Mathar_, Feb 21 2020
%e The length 4 inversion sequences avoiding (110, 120, 021) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0022, 0023, 0100, 0101, 0102, 0103, 0111, 0112, 0113, 0122, 0123.
%p a:= proc(n) option remember; `if`(n<3, n!,
%p ((5*n^2-6*n-2)*a(n-1)-(4*n-2)*(n-1)*a(n-2))/(n^2-4))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Mar 11 2017
%t a[n_] := 1 + Sum[(k - t - 1) (k - t)/(n - t + 1)* Binomial[2 n - k - t + 1, n - k + 1], {t, n - 1}, {k, t + 2, n + 1}]; Array[a, 28, 0] (* _Robert G. Wilson v_, Feb 25 2017 *)
%Y Cf. A000108, A114277, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
%K nonn
%O 0,3
%A _Megan A. Martinez_, Jan 16 2017
%E a(10)-a(12) from _Alois P. Heinz_, Feb 24 2017
%E a(13) onward _Robert G. Wilson v_, Feb 25 2017
|
