|
%I #31 Sep 08 2022 08:46:18
%S 1,1,2,6,21,81,332,1420,6266,28318,130412,609808,2887582,13818590,
%T 66726628,324713196,1590853485,7840315329,38843186366,193342353214,
%U 966409013021,4848846341569,24412146213116,123290812268404,624448756434476,3171046361310556
%N Number of length n inversion sequences avoiding the patterns 100, 110, 120, 201, and 210.
%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_k. This is the same as the set of length n inversion sequences avoiding 100, 110, 120, 201, and 210.
%H Alois P. Heinz, <a href="/A279565/b279565.txt">Table of n, a(n) for n = 0..1372</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.
%F G.f.: 3/(4-4*sin(asin((27*x+11)/16)/3)). - _Vladimir Kruchinin_, Mar 25 2019
%F a(n) = (1/n)*Sum_{m=1..n} m*Sum_{k=0..n-m} C(k,n-m-k)*C(n+k-1,k), n>0, a(0)=1. - _Vladimir Kruchinin_, Mar 26 2019
%F a(n) ~ 3^(3*n + 1/2) / (2^(7/2) * sqrt(Pi) * n^(3/2) * 5^(n - 1/2)). - _Vaclav Kotesovec_, Oct 07 2021
%e The length 4 inversion sequences avoiding (100, 110, 120, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0102, 0103, 0111, 0112, 0113, 0121, 0122, 0123.
%p a:= proc(n) option remember; `if`(n<3, n!,
%p ((n-1)*(17*n-28)*a(n-1) +(49*n^2-185*n+196)*a(n-2)
%p +(3*(3*n-7))*(3*n-8)*a(n-3)) / (5*n*(n-1)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Feb 22 2017
%t a[n_] := a[n] = If[n < 3, n!, (((n - 1)*(17*n - 28)*a[n-1] + (49*n^2 - 185*n + 196)*a[n-2] + (3*(3*n - 7))*(3*n - 8)*a[n-3]) / (5*n*(n - 1)))]; Array[a, 30, 0] (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)
%t Join[{1}, Table[(1/n)*Sum[m*Sum[Binomial[k, n-m-k]*Binomial[n+k-1, k], {k, 0, n-m}], {m, 1, n}], {n, 1, 30}]] (* _G. C. Greubel_, Mar 29 2019 *)
%o (Maxima)
%o a(n):=if n=0 then 1 else sum(m*sum(binomial(k,n-m-k)*binomial(n+k-1,k),k,0,n-m),m,1,n)/n /* _Vladimir Kruchinin_, Mar 26 2019 */
%o (PARI) my(x='x+O('x^30)); Vec(round(3/(4-4*sin(asin((27*x+11)/16)/3)))) \\ _G. C. Greubel_, Mar 29 2019
%o (Magma) I:=[6, 21, 81]; [1,1,2] cat [n le 3 select I[n] else ( (n+1)*(17*n+6)*Self(n-1) +(49*n^2+11*n+22)*Self(n-2) +3*(3*n-1)*(3*n-2)*Self(n-3) )/(5*(n+2)*(n+1)) : n in [1..30]]; // _G. C. Greubel_, Mar 29 2019
%o (Sage) [1] +[(1/n)*(sum(sum(k*binomial(j,n-k-j)*binomial(n+j-1,j) for j in (0..n-k)) for k in (1..n))) for n in (1..30)] # _G. C. Greubel_, Mar 29 2019
%Y Cf. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.
%K nonn
%O 0,3
%A _Megan A. Martinez_, Feb 09 2017
%E a(10)-a(25) from _Alois P. Heinz_, Feb 22 2017
|
