|
|
A279565
|
|
Number of length n inversion sequences avoiding the patterns 100, 110, 120, 201, and 210.
|
|
25
|
|
|
1, 1, 2, 6, 21, 81, 332, 1420, 6266, 28318, 130412, 609808, 2887582, 13818590, 66726628, 324713196, 1590853485, 7840315329, 38843186366, 193342353214, 966409013021, 4848846341569, 24412146213116, 123290812268404, 624448756434476, 3171046361310556
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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_k. This is the same as the set of length n inversion sequences avoiding 100, 110, 120, 201, and 210.
|
|
LINKS
|
|
|
FORMULA
|
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
a(n) ~ 3^(3*n + 1/2) / (2^(7/2) * sqrt(Pi) * n^(3/2) * 5^(n - 1/2)). - Vaclav Kotesovec, Oct 07 2021
|
|
EXAMPLE
|
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.
|
|
MAPLE
|
a:= proc(n) option remember; `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)))
end:
|
|
MATHEMATICA
|
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 *)
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 *)
|
|
PROG
|
(Maxima)
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 */
(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
(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
(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
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|