Bounds on Superpatterns Containing all Layered Permutations

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).