Separable d-permutations and guillotine partitions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 $d$-dimensional permutations and guillotine partitions of a $2^{d-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 results on avoided patterns in permutations.
20 pages, 13 figures

Keywords

Combinatorics, 05A05, 05A15 (Primary); 05C30, 68R05 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/157340

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0803.3414
 http://arxiv.org/abs/0803.3414

Collections

arXiv