login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032351 Number of permutations of length n which avoid the patterns 2143, 1324 (smooth permutations); or avoid the patterns 1342, 2431; etc. 3

%I #77 May 12 2022 17:48:51

%S 1,1,2,6,22,88,366,1552,6652,28696,124310,540040,2350820,10248248,

%T 44725516,195354368,853829272,3733693872,16333556838,71476391800,

%U 312865382004,1369760107576,5998008630244,26268304208032,115055864102504,503997820344464,2207927106851580,9673223726469136,42382192892577128,185702341264971696

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

%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.47.

%D R. P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.

%H 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 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 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 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 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 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 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 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 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 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 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 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 G.f.: (1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3).

%F G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (1 - x / (1 - x / (1 - x / ...))))))). - _Michael Somos_, Apr 18 2012

%F From _Gary W. Adamson_, Jul 11 2011: (Start)

%F a(n) = upper left term in n-th power of the following infinite square production matrix:

%F 1, 1, 0, 0, 0, 0, ...

%F 1, 2, 1, 0, 0, 0, ...

%F 1, 3, 1, 1, 0, 0, ...

%F 1, 4, 1, 1, 1, 0, ...

%F 1, 5, 1, 1, 1, 1, ...

%F ...

%F (End)

%F 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 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 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 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 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 88*x^5 + 366*x^6 + 1552*x^7 + ...

%p t1:=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);

%p series(t1,x,40);

%p seriestolist(%); # _N. J. A. Sloane_, Nov 09 2016

%t 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 (PARI) x='x+O('x^44) /* that many terms */

%o gf=(1-5*x+3*x^2+x^2*sqrt(1-4*x))/(1-6*x+8*x^2-4*x^3);

%o Vec(gf) /* show terms */ /* _Joerg Arndt_, Apr 20 2011 */

%o (Maxima)

%o 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 Cf. A053617.

%K nonn,easy,nice

%O 0,3

%A _Miklos Bona_

%E More terms from _Erich Friedman_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)