On the number of permutations avoiding a given pattern

DOI10.1006/JCTA.1999.3002zbMATH Open0948.05003OpenAlexW2021480278MaRDI QIDQ1971017FDOQ1971017

Authors: Noga Alon, Ehud Friedgut 

Publication date: 19 November 2000

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcta.1999.3002

Recommendations

• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• The solution of a conjecture of Stanley and Wilf for all layered patterns
• Asymptotic enumeration of permutations avoiding generalized patterns
• Excluded permutation matrices and the Stanley-Wilf conjecture
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia

zbMATH Keywords

permutationpatternDavenport-Schinzel sequences

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial inequalities (05A20)

Cites Work

• Restricted permutations
• Title not available (Why is that?)
• Asymptotic values for degrees associated with strips of Young diagrams
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Permutations avoiding certain patterns: The case of length 4 and some generalizations
• Generalized Davenport-Schinzel sequences
• Title not available (Why is that?)
• The solution of a conjecture of Stanley and Wilf for all layered patterns

Cited In (35)

• Permutations avoiding sets of patterns with long monotone subsequences
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Strongly sublinear algorithms for testing pattern freeness
• Avoidance of boxed mesh patterns on permutations
• The number of permutations avoiding a set of generalized permutation patterns
• Pattern avoidance over a hypergraph
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Counting occurrences of 231 in an involution
• Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
• Quasirandom permutations
• Large deviations and ratio limit theorems for pattern-avoiding permutations
• Restricted \(k\)-ary words and functional equations
• On a conjecture about strong pattern avoidance
• Pattern avoidance in poset permutations
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Asymptotic enumeration of permutations avoiding generalized patterns
• On extremal permutations avoiding \(\omega_N=NN-1\dots 1\)
• Words over a finite alphabet avoiding 1243
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• On the sub-permutations of pattern avoiding permutations
• Finite automata and pattern avoidance in words
• A relation on 132-avoiding permutation patterns
• Permutations all of whose patterns of a given length are distinct
• Stieltjes moment sequences for pattern-avoiding permutations
• On avoiding 1233
• A simple proof for the exponential upper bound for some tenacious patterns
• Forbidden paths and cycles in ordered graphs and matrices
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• Permutation patterns are hard to count
• Shape avoiding permutations
• Problems and conjectures presented at the problem session. Assembled by Vincent Vatter.
• On permutation patterns with constrained gap sizes
• A probabilistic approach to consecutive pattern avoiding in permutations
• Avoiding consecutive patterns in permutations
• Title not available (Why is that?)

This page was built for publication: On the number of permutations avoiding a given pattern

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971017)