cp's OEIS Frontend

A032351 Number of permutations of length n which avoid the patterns 2143, 1324 (smooth permutations); or avoid the patterns 1342, 2431; etc.

%I A032351 #77 May 12 2022 17:48:51
%S A032351 1,1,2,6,22,88,366,1552,6652,28696,124310,540040,2350820,10248248,
%T A032351 44725516,195354368,853829272,3733693872,16333556838,71476391800,
%U A032351 312865382004,1369760107576,5998008630244,26268304208032,115055864102504,503997820344464,2207927106851580,9673223726469136,42382192892577128,185702341264971696
%N A032351 Number of permutations of length n which avoid the patterns 2143, 1324 (smooth permutations); or avoid the patterns 1342, 2431; etc.
%D A032351 S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
%D A032351 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.47.
%D A032351 R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.
%H A032351 H. Abe and S. Billey, <a href="http://www.math.washington.edu/~billey/papers/abe.billey.pdf">Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry</a>, 2014.
%H A032351 George Balla, Ghislain Fourier, and Kunda Kambaso, <a href="https://arxiv.org/abs/2205.01747">PBW filtration and monomial bases for Demazure modules in types A and C</a>, arXiv:2205.01747 [math.RT], 2022.
%H A032351 C. Bean, M. Tannock and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.08155">Pattern avoiding permutations and independent sets in graphs</a>, arXiv:1512.08155 [math.CO], 2015. See Eq. (2).
%H A032351 Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
%H A032351 Miklos Bona, <a href="https://doi.org/10.37236/1369">The permutation classes equinumerous to the smooth class</a>, Electron. J. Combin., 5 (1998), no. 1, Research Paper 31, 12 pp.
%H A032351 M. Bousquet-Mélou and S. Butler, <a href="https://arxiv.org/abs/math/0603617">Forest-like permutations</a>, arXiv:math/0603617 [math.CO], 2006.
%H A032351 Rocco Chirivì, Xin Fang, and Ghislain Fourier, <a href="https://doi.org/10.1007/s00031-020-09558-4">Degenerate Schubert varieties in type A</a>, Transformation Groups (2020).
%H A032351 Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
%H A032351 E. Rowland and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013-2014.
%H A032351 Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.
%H A032351 A. Woo and A. Yong, <a href="https://arxiv.org/abs/math/0409490">When is a Schubert variety Gorenstein?</a>, arXiv:math/0409490 [math.AG], 2004.
%H A032351 A. Woo and A. Yong, <a href="https://doi.org/10.1016/j.aim.2005.11.010">When is a Schubert variety Gorenstein?</a>, Advances in Mathematics, Volume 207, Issue 1, 1 December 2006, Pages 205-220.
%F A032351 G.f.: (1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3).
%F A032351 G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (1 - x / (1 - x / (1 - x / ...))))))). - _Michael Somos_, Apr 18 2012
%F A032351 From _Gary W. Adamson_, Jul 11 2011: (Start)
%F A032351 a(n) = upper left term in n-th power of the following infinite square production matrix:
%F A032351   1, 1, 0, 0, 0, 0, ...
%F A032351   1, 2, 1, 0, 0, 0, ...
%F A032351   1, 3, 1, 1, 0, 0, ...
%F A032351   1, 4, 1, 1, 1, 0, ...
%F A032351   1, 5, 1, 1, 1, 1, ...
%F A032351   ...
%F A032351 (End)
%F A032351 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
%F A032351 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
%F A032351 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
%F A032351 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
%e A032351 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 88*x^5 + 366*x^6 + 1552*x^7 + ...
%p A032351 t1:=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
%p A032351 series(t1,x,40);
%p A032351 seriestolist(%); # _N. J. A. Sloane_, Nov 09 2016
%t A032351 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_ *)
%o A032351 (PARI) x='x+O('x^44) /* that many terms */
%o A032351 gf=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);
%o A032351 Vec(gf) /* show terms */ /* _Joerg Arndt_, Apr 20 2011 */
%o A032351 (Maxima)
%o A032351 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 */
%Y A032351 Cf. A053617.
%K A032351 nonn,easy,nice
%O A032351 0,3
%A A032351 _Miklos Bona_
%E A032351 More terms from _Erich Friedman_