|
|
A032351
|
|
Number of permutations of length n which avoid the patterns 2143, 1324 (smooth permutations); or avoid the patterns 1342, 2431; etc.
|
|
3
|
|
|
1, 1, 2, 6, 22, 88, 366, 1552, 6652, 28696, 124310, 540040, 2350820, 10248248, 44725516, 195354368, 853829272, 3733693872, 16333556838, 71476391800, 312865382004, 1369760107576, 5998008630244, 26268304208032, 115055864102504, 503997820344464, 2207927106851580, 9673223726469136, 42382192892577128, 185702341264971696
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.47.
R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3).
G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (1 - x / (1 - x / (1 - x / ...))))))). - Michael Somos, Apr 18 2012
a(n) = upper left term in n-th power of the following infinite square production matrix:
1, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 3, 1, 1, 0, 0, ...
1, 4, 1, 1, 1, 0, ...
1, 5, 1, 1, 1, 1, ...
...
(End)
Recurrence: (n-2)*a(n) = 2*(5*n-13)*a(n-1) - 4*(8*n-25)*a(n-2) + 12*(3*n-10)*a(n-3) - 8*(2*n-7)*a(n-4). - Vaclav Kotesovec, Aug 24 2014
a(n) ~ 1/11 * (1 - 5*r + 3*r^2 + r^2*sqrt(1-4*r)) *(25 - 44*r + 24*r^2) / r^n, where r = 1/6*(4 - 2/(-17 + 3*sqrt(33))^(1/3) + (-17 + 3*sqrt(33))^(1/3)) = 0.228155493653961819214572... is the root of the equation -1 + 6*r - 8*r^2 + 4*r^3 = 0. - Vaclav Kotesovec, Aug 24 2014
a(n) = (Sum_{m=0..n-2} (m+3)*(Sum_{k=0..m/2} Sum_{j=0..m-2*k-1} 2^j * binomial(j+k, k) * binomial(m-j, 2*k+1)) * binomial(2*n-m-2,n) + binomial(2*n,n))/(n+1). - Vladimir Kruchinin, Sep 19 2014
|
|
EXAMPLE
|
1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 88*x^5 + 366*x^6 + 1552*x^7 + ...
|
|
MAPLE
|
t1:=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
series(t1, x, 40);
|
|
MATHEMATICA
|
Table[(Sum[(m+3)*(Sum[Sum[2^j*Binomial[j+k, k]*Binomial[m-j, 2*k+1], {j, 0, m-2*k-1}], {k, 0, m/2}]) * Binomial[2*n-m-2, n], {m, 0, n-2}] + Binomial[2*n, n])/(n+1), {n, 0, 20}] (* Vaclav Kotesovec, Sep 19 2014, after Vladimir Kruchinin *)
|
|
PROG
|
(PARI) x='x+O('x^44) /* that many terms */
gf=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
Vec(gf) /* show terms */ /* Joerg Arndt, Apr 20 2011 */
(Maxima)
a(n):=(sum((m+3)*(sum(sum(2^(j)*binomial(j+k, k)*binomial(m-j, 2*k+1), j, 0, m-2*k-1), k, 0, m/2))*binomial(2*n-m-2, n), m, 0, n-2)+binomial(2*n, n))/(n+1); /* Vladimir Kruchinin, Sep 19 2014 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|