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!)
A088921 The number of 321- and 2143-avoiding permutations of length n. 2
1, 2, 5, 13, 33, 80, 185, 411, 885, 1862, 3853, 7881, 15993, 32284, 64945, 130359, 261293, 523282, 1047397, 2095781, 4192721, 8386792, 16775145, 33552083, 67106213, 134214750, 268432125, 536867201, 1073737705, 2147479092 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
That is, both the patterns 321 and 2143 are to be avoided. - N. J. A. Sloane, Oct 21 2010.
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.
Also, number of 1324-avoiding circular permutations on [n+1].
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
LINKS
Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
S. Billey, W. Jockusch and R. P. Stanley, Some combinatorial properties of Schubert polynomials, Journal of Algebraic Combinatorics 2(4):345-374, 1993.
D. Callan, Pattern avoidance in circular permutations, arXiv:math/0210014 [math.CO], 2002.
K. Eriksson and S. Linusson, Combinatorics of Fulton's essential set, Duke Mathematical Journal 85(1) (1996) 61-76.
Juan B. Gil and Jessica A. Tomasko, Restricted Grassmannian permutations, arXiv:2112.03338 [math.CO], 2021.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
A. Vella, Pattern avoidance in permutations: linear and cyclic orders, Electron. J. Combin. 9 (2002/03), no. 2, #R18, 43 pp.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
FORMULA
a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1.
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
MATHEMATICA
Table[2^(n + 1) - Binomial[n + 1, 3] - 2 n - 1, {n, 30}] (* or *)
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 *)
PROG
(PARI) a(n) = 2^(n+1) - binomial(n+1, 3) - 2*n - 1 \\ Michel Marcus, Jul 11 2013
CROSSREFS
Cf. A000325.
Sequence in context: A366117 A027929 A001659 * A005183 A005348 A369578
KEYWORD
easy,nonn
AUTHOR
Antoine Vella (avella(AT)math.uwaterloo.ca), Oct 23 2003
STATUS
approved

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 07:20 EDT 2024. Contains 371235 sequences. (Running on oeis4.)