Separable d-Permutations and Guillotine Partitions

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 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 several results on patterns in permutations.