The Packing Density of Other Layered Permutations

Abstract

In this paper the packing density of various layered permutations is calculated, thus solving some problems suggested by Albert, Atkinson, Handley, Holton $\&$ Stromquist [Electron. J. Combin. 9 (2002), $\#$R5]. Specifically, the density is found for layered permutations of type $[m_1, \ldots, m_r]$ when $\log(r+1)\le \min\{ m_i\}$. It is also shown how to derive good estimates for the packing density of permutations of type $[k,1,k]$ when $k\ge 3$. Both results are based on establishing the number of layers in near optimal permutations using a layer-merging technique.