On Packing Densities of Permutations
Open Access
- 1 January 2002
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 9 (1) , R5
Abstract
The density of a permutation pattern $\pi$ in a permutation $\sigma$ is the proportion of subsequences of $\sigma$ of length $|\pi|$ that are isomorphic to $\pi$. The maximal value of the density is found for several patterns $\pi$, and asymptotic upper and lower bounds for the maximal density are found in several other cases. The results are generalised to sets of patterns and the maximum density is found for all sets of length $3$ patterns.
Keywords
This publication has 4 references indexed in Scilit:
- Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar MapsJournal of Combinatorial Theory, Series A, 1997
- Classification of Forbidden Subsequences of Length 4European Journal of Combinatorics, 1996
- Restricted PermutationsEuropean Journal of Combinatorics, 1985
- On the Ramsey multiplicities of graphs—problems and recent resultsJournal of Graph Theory, 1980