|
| |
|
|
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
|
H. Abe and S. Billey, Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry, 2014; http://www.math.washington.edu/~billey/papers/abe.billey.pdf
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.47.
A. Woo and A. Yong, "When is a Schubert variety Gorenstein?", preprint 2004.
|
|
|
LINKS
|
Table of n, a(n) for n=0..29.
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015. See Eq. (2).
Miklos Bona, The permutation classes equinumerous to the smooth class, Electron. J. Combin., 5 (1998), no. 1, Research Paper 31, 12 pp.
M. Bousquet-Mélou and S. Butler, Forest-like permutations.
E. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635, 2013
Wikipedia, Permutation classes avoiding two patterns of length 4.
A. Woo and A. Yong, When is a Schubert variety Gorenstein?.
|
|
|
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, ...
...
- Gary W. Adamson, Jul 11 2011
HANKEL transform is A011782. HANKEL transform of a(n+1) is A011782(n+1). INVERT transform of A026671 with 1 prepended. - Michael Somos, Apr 18 2012
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);
seriestolist(%); # N. J. A. Sloane, Nov 09 2016
|
|
|
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
|
Cf. A053617.
Sequence in context: A165535 A319028 A165536 * A165537 A165538 A165539
Adjacent sequences: A032348 A032349 A032350 * A032352 A032353 A032354
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
Miklos Bona (bona(AT)math.ufl.edu)
|
|
|
EXTENSIONS
|
More terms from Erich Friedman
|
|
|
STATUS
|
approved
|
| |
|
|
