Separable d-Permutations and Guillotine Partitions
Separable d-Permutations and Guillotine Partitions
复制标题
可分离的 d-排列和断头台分区
DOI：
10.1007/s00026-010-0043-8
复制
发表时间：
2008
影响因子：
0.5
通讯作者：
T. Mansour
中科院分区：
文献类型：
--
作者：
Andrei Asinowski;T. Mansour
我们用禁止模式来描述可分离的多维排列，并通过生成函数、递归公式和显式公式来枚举它们。我们发现了多维排列和盒子的断头台分割之间的联系。特别地，构造了可分离的d维排列和2d-1维盒子的断头台分区之间的双射。我们还研究了在某些限制下与断头台分区相关的枚举问题，揭示了与其他组合结构的联系。这允许我们获得关于排列模式的几个结果。
We characterize separable multidimensional permutations in terms of forbidden patterns and enumerate them by means of generating function, recursive formula, and explicit formula. We find a connection between multidimensional permutations and guillotine partitions of a box. In particular, a bijection between separable d-dimensional permutations and guillotine partitions of a 2d-1-dimensional box is constructed. We also study enumerating problems related to guillotine partitions under certain restrictions revealing connections to other combinatorial structures. This allows us to obtain several results on patterns in permutations.