|
|
A279557
|
|
Number of length n inversion sequences avoiding the patterns 110, 120, and 021.
|
|
25
|
|
|
1, 1, 2, 6, 20, 68, 233, 805, 2807, 9879, 35073, 125513, 452389, 1641029, 5986994, 21954974, 80884424, 299233544, 1111219334, 4140813374, 15478839554, 58028869154, 218123355524, 821908275548, 3104046382352, 11747506651600, 44546351423300, 169227201341652
(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_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.
|
|
LINKS
|
|
|
FORMULA
|
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).
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).
Assuming the conjecture a(n) ~ (64/3)*4^n/((4*n+7)^(3/2)*sqrt(Pi)). - Peter Luschny, Feb 24 2017
G.f.: (sqrt(1-4*x)+2*x-1)*(2*x-1)/(2*(1-x)*x^2). (End)
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
|
|
EXAMPLE
|
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.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<3, n!,
((5*n^2-6*n-2)*a(n-1)-(4*n-2)*(n-1)*a(n-2))/(n^2-4))
end:
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|