<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Separable d-Permutations and Guillotine Partitions
Andrei Asinowski1 and Toufik Mansour2
1Caesarea Rothschild Institute, University of Haifa, Haifa 31905, Israel
andrei@cri.haifa.ac.il
2Department of Mathematics, University of Haifa, Haifa 31905, Israel
toufik@math.haifa.ac.il
Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010
AMS Subject Classification: 05A05, 05A15, 05C30
Abstract:
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.
Keywords: d-permutations, separable permutations, patterns in permutations, guillotine partitions, binary trees, Schr¨oder paths

References:

1. Ackerman, E., Barequet, G., Pinter, R.Y.: A bijection between permutations and floorplans, and its applications. Discrete Appl. Math. 154(12), 1674--–1684 (2006)

2. Ackerman, E., Barequet, G., Pinter, R.Y., Romik, D.: The number of guillotine partitions in d dimensions. Inform. Process. Lett. 98(4), 162--–167 (2006)

3. Atkinson, M.D., Stitt, T.: Restricted permutations and the wreath product. Discrete Math. 259(1-3), 19--–36 (2002)

4. Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inform. Process. Lett. 65(5), 277--–283 (1998)

5. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Vol. 3. SIAM, Philadelphia (1999)

6. Elizalde, S.: The X-class and almost-increasing permutations. Ann. Combin. (to appear), arXiv:0710.5168v1 [math.CO]

7. Golumbic, M.C.: Personal communication.

8. Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/vnjas/sequences/.

9. Shapiro, L.: Stephens, A.B.: Bootstrap percolation, the Schröder numbers and the N-kings problem. SIAM J. Discrete Math. 4(2), 275--–280 (1991)

10. Stanley, R.: Enumerative Combinatorics, Volume 2. Cambridge University Press, Cambridge (1999)

11. Yao, B., Chen, H., Cheng, C.K., Graham, R.: Floorplan representations: complexity and connections. ACM Trans. Des. Automat. Electron. Systems 8(1), 55--–80 (2003)