TY - JOUR
T1 - Bounds on Superpatterns Containing all Layered Permutations
AU - Gray, Daniel
N1 - In the study of pattern containment, a $$k$$k-superpattern is a permutation which contains all $$k!$$k! permutations of length $$k$$k as a pattern. One may also consider restricted superpatterns, i.e.
PY - 2015/7
Y1 - 2015/7
N2 - 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).
AB - 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).
KW - Layered permutations
KW - Null-balanced binary trees
KW - Superpatterns
UR - https://doi.org/10.1007/s00373-014-1429-x
U2 - 10.1007/s00373-014-1429-x
DO - 10.1007/s00373-014-1429-x
M3 - Article
SN - 0911-0119
VL - 31
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
ER -