The Packing Density of Other Layered Permutations

Peter A. Hästö


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.

Full Text: