Article
Bounds on Superpatterns Containing all Layered Permutations
Graphs and Combinatorics
(2015)
Abstract
In the study of pattern containment, a kk -superpattern is a permutation which contains all k!k! permutations of length kk as a pattern. One may also consider restricted superpatterns, i.e. a permutation which contains, as a pattern, every element in some subclass of the set of permutations of length kk . Here, we find lower and upper bounds on a superpattern which contains all layered kk -permutations. Also, we exhibit a connection between the sum of depths of null-balanced binary trees on kk vertices, as defined in (Proceedings of American Conference on Applied Mathematics, Cambridge, MA, pp 377–381 2012).
Keywords
- Layered permutations,
- Superpatterns,
- Null-balanced binary trees
Disciplines
Publication Date
July, 2015
DOI
10.1007/s00373-014-1429-x
Citation Information
Daniel Gray. "Bounds on Superpatterns Containing all Layered Permutations" Graphs and Combinatorics Vol. 31 Iss. 4 (2015) p. 941 - 952 ISSN: 1435-5914 Available at: http://works.bepress.com/daniel-gray/1/