cp's OEIS Frontend

A088921 The number of 321- and 2143-avoiding permutations of length n.

%I A088921 #37 Apr 29 2025 07:55:50
%S A088921 1,2,5,13,33,80,185,411,885,1862,3853,7881,15993,32284,64945,130359,
%T A088921 261293,523282,1047397,2095781,4192721,8386792,16775145,33552083,
%U A088921 67106213,134214750,268432125,536867201,1073737705,2147479092
%N A088921 The number of 321- and 2143-avoiding permutations of length n.
%C A088921 That is, both the patterns 321 and 2143 are to be avoided. - _N. J. A. Sloane_, Oct 21 2010.
%C A088921 321- and 2143-avoiding permutations of length n are in one-to-one correspondence with simple Dyck paths of semilength n (a Dyck path is simple if it has at most one long upward edge or at most one long downward edge, an edge being "long" if it consists of at least two steps). They are the Grassmannian permutations and their inverses. They can also be characterized as those permutations whose essential set is contained in one row or one column. This sequence also enumerates the cyclic arrangements of 1, 2, ... n+1 which avoid the cyclic arrangement 1234.
%C A088921 Also, number of 1324-avoiding circular permutations on [n+1].
%C A088921 Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k) and e(i) != e(k). [Martinez and Savage, 2.9] - _Eric M. Schmidt_, Jul 17 2017
%H A088921 Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, <a href="https://arxiv.org/abs/1705.04109">Automatic discovery of structural rules of permutation classes</a>, arXiv:1705.04109 [math.CO], 2017.
%H A088921 S. Billey, W. Jockusch and R. P. Stanley, <a href="http://www.math.washington.edu/~billey/papers/bjs.pdf">Some combinatorial properties of Schubert polynomials</a>, Journal of Algebraic Combinatorics 2(4):345-374, 1993.
%H A088921 D. Callan, <a href="http://arXiv.org/abs/math.CO/0210014">Pattern avoidance in circular permutations</a>, arXiv:math/0210014 [math.CO], 2002.
%H A088921 K. Eriksson and S. Linusson, <a href="http://dx.doi.org/10.1215/S0012-7094-96-08502-6">Combinatorics of Fulton's essential set</a>, Duke Mathematical Journal 85(1) (1996) 61-76.
%H A088921 Juan B. Gil and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2112.03338">Restricted Grassmannian permutations</a>, arXiv:2112.03338 [math.CO], 2021.
%H A088921 Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%H A088921 Permutation Pattern Avoidance Library (PermPAL), <a href="https://permpal.com/perms/basis/012_2301/">Av(123,3412)</a>
%H A088921 A. Vella, <a href="https://doi.org/10.37236/1690">Pattern avoidance in permutations: linear and cyclic orders</a>, Electron. J. Combin. 9 (2002/03), no. 2, #R18, 43 pp.
%H A088921 Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.
%F A088921 a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1.
%F A088921 G.f.: x*(2*x^4-5*x^3+7*x^2-4*x+1)/((1-2*x)*(1-x)^4). - _Emeric Deutsch_, Feb 22 2004
%t A088921 Table[2^(n + 1) - Binomial[n + 1, 3] - 2 n - 1, {n, 30}] (* or *)
%t A088921 Rest@ CoefficientList[Series[x (2 x^4 - 5 x^3 + 7 x^2 - 4 x + 1)/((1 - 2 x) (1 - x)^4), {x, 0, 30}], x] (* _Michael De Vlieger_, May 13 2017 *)
%o A088921 (PARI) a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1 \\ _Michel Marcus_, Jul 11 2013
%Y A088921 Cf. A000325.
%K A088921 easy,nonn
%O A088921 1,2
%A A088921 Antoine Vella (avella(AT)math.uwaterloo.ca), Oct 23 2003