On the Numb er of Rectangular Partitions Eyal Ackerman Gill Barequet Ron Y. Pinter Abstract How many ways can a rectangle be partitioned into smaller ones? We study two variants of this problem: when the partitions are constrained to lie on n given points (no two of which are corectilinear), and when there are no such constraints and all we require is that the number of (non-intersecting) segments is n. In the first case, when the order (permutation) of the points conforms with a certain property, the number of partitions is the (n + 1)st Baxter number, B (n + 1); the number of permutations conforming with the property is the (n - 1)st Schr¨der number; and the number of o guillotine partitions is the nth Schr¨der number. In o the second case, it is known [22] that the number of partitions and the number of guillotine partitions correspond to the Baxter and Schr¨der numbers, respeco tively. Our contribution is a bijection between permutations and partitions. Our results provide interesting and new geometric interpretations to both Baxter and Schr¨der numbers and suggest insights regarding the ino tricacies of the interrelations. Keywords: Rectangular partitions, guillotine partitions, Baxter permutations, Schr¨der numbers, quasio monotone permutations. 1 Intro duction Given a rectangle R, a Rectangular Partition (RP) is a subdivision of R into rectangles by non-intersecting axis-parallel segments. We investigate the number of different rectangular partitions for two variants of the problem: First, we consider the point-free variant, where RP simply comprises n segments and two partitions are considered different if the relative ordering of the segments is not the same. Second, we consider point-constrained rectangular partitions, where we are given a set P of n noncorectilinear points inside R and every point in P must lie on (exactly) one segment of RP. The number of point-free rectangular partitions has been studied elsewhere under a different name: Yao et al. [21, 22] have shown that the number of mosaic floorplans containing n blocks is the number of Baxter per Dept. of Computer Science, Technion--Israel Institute of Technology, Haifa 32000, Israel. E-mail: [ackerman|barequet|pinter]@cs.technion.ac.il mutations on n. They have provided two alternative proofs of this fact: the first, by obtaining the same recursive formula used by Chung et al. [4] in their analysis of the number of Baxter permutations; and the second, by showing a bijection between mosaic floorplans and twin binary trees, whose number is also known [7] to be the number of Baxter permutations. Our contribution is a simple and direct bijection between mosaic floorplans (point-free partitions in our terminology) and Baxter permutations. For point-constrained rectangular partitions it turns out that the number of rectangular partitions, denoted by #RP c , depends on the relative order of the points in P . We represent this order by a permutation on n (reflecting the order of y -coordinates with respect to the x-coordinates), and show that as long as avoids forbidden subsequences with the same comparisons as 2413 and 3142, #RP c is the (n + 1)st Baxter number. Inspired by the way a permutation of this class can be recursively constructed, we name them quasimonotone permutations; we observe that their number is known to be the (n - 1)st Schr¨der number. We also o show that when only guil lotine partitions are allowed, then no matter what the permutation of the points is, the number of different rectangular partitions is the nth Schr¨der number. o Point-constrained partitions are related to the optimization problem of finding the minimum edge-length rectangular partition of a rectangle with n noncorectilinear points inside it (known as RGNLP ). It is shown in [2] (as we have observed independently) that an optimal solution of an instance of RGNLP must be composed of exactly n non-intersecting segments, yielding the relation to point-constrained rectangular partitions. The rest of this paper is organized as follows. In Section 2 we briefly describe some related work on rectangular partitions. In Section 3 we give a short background on Baxter and Schr¨der numbers. o The bijection between point-free partitions and Baxter permutations is described in Section 4. In Section 5 we consider the number of different point-constrained rectangular partitions: we start by describing a method to constructively enumerate them; then we discuss guillotine partitions; next we show that for the identity permutation of n points #RP c is the (n + 1)st Baxter number, and finally we generalize the analysis from identity to quasi-monotone permutations and observe Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 736 that the number of such permutations is the (n - 1)st Schr¨der number. In Section 6 we discuss the relation o between point-free and point-constrained partitions. We conclude in Section 7. 2 Related Work Sakanushi and Ka jitani [17] were the first to consider the number of distinct (mosaic) floorplans. They found a recursive formula for this number, but did not recognized it to be the same recursive formula suggested by Chung et al. [4] in their analysis of the number of Baxter permutations. Yao et al. [21] were the first to show that the number of distinct floorplans containing n blocks is the number of Baxter permutations on n. They have derived the same recursive formula, however, by using a different analysis. Moreover, in the journal version of their work [22] they have provided an alternative proof: a bijection between floorplans and twin binary trees. The number of twin binary trees is known [7] to be the number of Baxter permutations. Yao et al. have also considered slicing floorplans (guillotine partitions in our terminology) and proved that their number is the nth Schr¨der number. o To the best of our knowledge, enumerative aspects of point-constrained rectangular partitions (as defined above) have never been studied before. However, there is a considerable amount of work that concerns optimization problems related to rectangular partitions, the most general of which is: Partition a rectilinear (i.e., axis-paral lel) polygon which encloses a set of "holes" (non-intersecting rectilinear polygons) into rectangles in a way that minimizes the total length of the edges participating in the partition. (Other criteria, e.g., obtaining the minimum number of rectangles, have also been considered.) One application of this problem is in the area of integrated-circuit design, e.g., in MIT's "PI" system [16]: Once the electronic modules have been placed on the chip, the routing area is partitioned into rectangles (channels), in order to simplify signal wires routing. This stage is known as "channel definition," and the minimum edge-length criterion was chosen since it results in more "natural-looking" rectangles. The partitioning problem where the holes are degenerate, i.e., a hole is a point and the bounding rectilinear polygon is a rectangle, is known as RGP (partitioning a rectangle with possibly-corectilinear points). This problem has applications to stock (or die) cutting in the presence of material defects. RGP, similarly to most of the polygon partitioning problems mentioned above (but unlike RGNLP), was shown to be NP-hard [13]. Over the years several approximation algorithms for RGP were suggested (see, e.g., [6, 8, 9, 10, 12]), including a polynomial-time approximation scheme [3, 14]. de Meneses and de Souza [5] suggested an integer programming formulation of RGP, and used this formula- tion and integer programming techniques to find exact solutions for medium sized instances of RGP. In [2], Calheiros, Lucena, and de Souza presented a reduced integer programming formulation for RGNLP instances. 3 Baxter and Schr¨der Numb ers o 3.1 Baxter numb ers. The nth Baxter number is the number of Baxter permutations on n. A Baxter permutation on n can be defined as a permutation = (1 , 2 , 3 , . . . , n ) that satisfies the following two conditions: For every 1 i < j < k < l n: 1. If i + 1 = l and j > l then k > l ; and 2. If l + 1 = i and k > i then j > i . For example, for n = 4, (3,1,4,2) and (2,4,1,3) are the only non-Baxter permutations. This class of permutations was introduced by Baxter [1] in the context of fixed points of the composite of commuting functions. Chung et al. [4] showed that the number of Baxter permutations on n is n+1 n+1 n+1 n n-1 r r r +1 r +2 D n+1 (3.1) B(n) = +1 =0 1 2 ulucq and Guibert [7] have shown one-toone correspondences between Baxter permutations, twin binary trees, and three non-intersecting paths on a grid. The first Baxter numbers are {0, 1, 2, 6, 22, 92, 422, 2074, . . .}. o 3.2 Schr¨der numb ers. The (large) Schr¨der numo bers arise in several enumerative combinatorial problems. One example is the number of paths on a grid from (0, 0) to (n, n), that stay below the line y = x + 1 and use only the steps (1, 0), (0, 1), and (1, 1). Other examples can be found in [19]. The first Schr¨der numbers o are {1, 2, 6, 22, 90, 394, 1806, . . .}. 4 Point-Free Partitions A point-free rectangular partition of a rectangle R is a partition of R into rectangles by non-intersecting rectilinear segments. Throughout this section, unless stated otherwise, the term `partitions' refers to pointfree rectangular partitions, and n marks the number of rectangles in a partition (it is easy to see that the number of rectangles is the number of segments plus 1). In order to count the number of different partitions (into n rectangles), we must first define equivalence of partitions. We follow the definition of Sakanushi et al. [17]: A top-, left-, right-, or bottom-seg-rect relation between a segment s and a rectangle r exists if s supports r from the respective direction. Two partitions are equivalent if there is a labeling of their rectangles and segments such that they hold the same seg-rect relations. 737 2 1 3 4 5 6 Observation 4.2. If rectangle r1 is next to rectangle r2 according to one of the two orders, then there is a segment that supports both r1 and r2 . Next, we prove that is indeed a one-to-one mapping from partitions to Baxter permutations. Lemma 4.1. Given a partition x with n rectangles, (x) is a Baxter permutation on n. Proof. Suppose (x) = 1 2 . . . n is not a Baxter permutation. Then there are four indices 1 i < j < k < l n such that either: (1) k < i + 1 = l < j ; or (2) j < l + 1 = i < k . Assume the first case holds, and choose w.l.o.g. j and k such that k = j + 1. According to observations 4.1 and 4.2 rectangle i is left of rectangle l , and some segment s1 supports both of them. Similarly, rectangle j is above rectangle k , and some segment s2 supports both of them. According to Observation 4.1 rectangle k is to the left of rectangle l and below rectangle i . Similarly, rectangle j is to the right of rectangle i and above rectangle l . Thus, s1 and s2 must intersect. The proof in the second case is similar and is thus omitted. Lemma 4.2. Given two partitions x1 and x2 , (x1 ) = (x2 ) then x1 and x2 are equivalent. if (a) (b) (c) Figure 1: Enumerating rectangles according to their deletion order from the top-left corner. Definition 4.1. A rectangle r1 is above a rectangle r2 if: (1) There is a segment s such that there is a bottom-seg-rect relation between r1 and s and a top-segrect relation between r2 and s; or (2) there is a rectangle r3 such that r3 is above r2 and r1 is above r3 . The relation left of is defined similarly. 4.1 A bijection b etween Baxter p ermutations and p oint-free partitions. As we have mentioned in the introduction, there is a bijection between point-free partitions and twin binary trees [22], and a bijection between twin binary trees and Baxter permutations [7]. Here we present a direct bijection between Baxter permutations and point-free partitions. We first describe a one-to-one mapping from point-free partitions to Baxter permutations. Then we show a one-to-one mapping in the opposite direction. Proof. By induction on the number of rectangles n. Let x1 (resp., x2 ) be the partition we get by deleting the top-left rectangle of x1 (resp., x2 ), and let s1 4.1.1 A one-to-one mapping from p oint-free (resp., s2 ) be the segment we `slide' in order to delete partitions to Baxter p ermutations. Given a par- the rectangle. Then s1 and s2 must have the same tition, we can delete its top-left rectangle by `sliding' orientation, otherwise the numbers 1 and 2 will have either the right edge of the rectangle to the left (see Fig- different orders in (x1 ) and (x2 ). Every pair of ure 1(a)), or its bottom edge upwards (see Figure 1(b)). rectangles in x1 (resp., x2 ) hold the same relation This operation is called block deletion [11], and it could (above or left of ) before and after the deletion, thus, 2 1 2 1 be defined similarly for every corner of the bounding (x ) = (x ). It follows that x = x and since s1 rectangle. In Figure 1 the rectangles are enumerated and s2 have the same orientation, x1 = x2 . according to their deletion order from the top-left cor4.1.2 A one-to-one mapping from Baxter p erner. We define a mapping from partitions to permutations mutations to p oint-free partitions. Algorithm BP2PFP (see Figure 2) constructs a partition of n rectin the following way: 1. Given a partition x we name its rectangles accord- angles given a Baxter permutation on n, by inserting ing the order in which they are deleted from the rectangles from the top-right corner and setting their boundaries according to the given permutation. See top-left corner. 2. (x) corresponds to the order in which the rectan- Figure 3 for an example. gles are deleted from the bottom-left corner. For example, the permutation that corresponds to the partition of Figure 1 is 413652. Observation 4.1. Rectangle r1 precedes rectangle r2 according to the top-left corner deletion order and r2 precedes r1 according to the bottom-left corner deletion order iff r1 is above r2 . Similarly, r1 precedes r2 according to both orders iff r1 is left of r2 . Lemma 4.3. There is a one-to-one mapping from Baxter permutations on n elements to partitions containing n rectangles. Proof. Let be a Baxter permutation on n, and let x be the output of Algorithm BP2PFP when applied to . Clearly x is a valid partition containing n rectangles. We will show that (x) = . It is easy to see that during the computation of (x), the rectangles are deleted 738 Input: A Baxter permutation = 1 2 . . . n Output: A point-free partition 1: Draw a rectangle 1 . 2: Construct an n × n grid within 1 . 3: for i 2 to n do 4: if i < i-1 then 5: Slice the top-right rectangle by a horizontal segment at the (i - 1)st level of the grid. 6: Name the newly-created rectangle i . 7: while the rectangle to the left of i has a label greater than i do 8: Extend rectangle i to the left. 9: else 10: Slice the top-right rectangle by a vertical segment at the (i - 1)st level of the grid. 11: Name the newly-created rectangle i . 12: while the rectangle below i has a label smaller than i do 13: Extend rectangle i downwards. Figure 2: Algorithm BP2PFP 3 1 1 4 4 4 (a) 4 (b) 41 (c) 413 2 5 5 6 3 1 4 6 3 1 4 4 1 3 6 (d) 4136 (e) 41365 (f ) 413652 Figure 3: Algorithm BP2PFP applied to 413652 B k B k a B k a c k+1 A k+1 k+1 (a) (b) (c) Figure 4: Illustrations for the proof of Lemma 4.3 from the bottom-left corner of x in the same order they were added to x in the course of Algorithm BP2PFP. Therefore, it is sufficient to prove that the order in which the rectangles of x are deleted from the top-left corner is 1, 2, . . . , n. It is clear that the rectangle labeled 1 is the first to be removed. Assume that for every 1 i k the rectangle labeled i is the ith rectangle which is removed from the top-left corner. We show next that the next rectangle to be deleted is the rectangle labeled k + 1. Suppose for contradiction that k + 1 precedes k in : = . . . , (k + 1), A, B , k , . . . , where A is a (possibly empty) sequence of integers greater than k + 1 and B is a (possibly empty) sequence of integers smaller than k (there are no other options since is a Baxter permutation). Figure 4(a) shows the partition after k was added. According to the induction hypothesis all the rectangles in B are removed before rectangle k is removed, so when k is removed the segment supporting its left edge also supports the left edge of k + 1. The bottom-right corner of k is either a `'-junction or a ` 'junction. In the second case k + 1 is the next rectangle to be deleted. A `'-junction can only be formed when the first rectangle greater than k and to the right of it in (denote it by c) is smaller than the rectangle below k and sharing the same segment as a right edge (denote this rectangle by a). Figures 4(b,c) describe the situation before and after c is added. Note that a is the last integer in A and k < c < a. If A is empty then a = k + 1; thus, there cannot be such a rectangle c. Otherwise, there must be an integer i such that k + 1 i c - 1, i is to the left of a in , and i + 1 is either c or to the right of c. Therefore i, a, k , i + 1 is a forbidden subsequence in . The proof for the second case (k precedes k +1 in ) is similar and is thus omitted. 5 Point-Constrained Partitions Given a rectangle R containing a set P of n noncorectilinear points, a point-constrained rectangular partition of R is a partition of R into rectangles, by n rectilinear segments, such that every point in P lies on exactly one segment (see Figure 5 for examples). Throughout this section, unless stated otherwise, the term `partitions' refers to point-constrained rectangular partitions. In the first part of this section we present a mechanism for exploring the space of partitions. Next, we define guillotine partitions and show that the number of guillotine partitions is the nth Schr¨der number. Then, we argue o that when both guillotine and nonguillotine partitions are considered #RP c depends only on the permutation of the points in P , and show that for the identity permu- (a) (R, P ) (b) A guillotine partition (c) A nonguillotine partition Figure 5: Point-constrained rectangular partitions 739 t p t p p It is thus possible to generate and iterate over all the partitions of (R, P ) by traversing G(R, P ) by, say, a standard depth- (or breadth-) first search. 5.2 Guillotine partitions. (a) x (b) Flip(x, p) (c) Rotate(x, t) Definition 5.3. In a guillotine partition the segments can be ordered so that when the partition is executed according to that order, the current segment always c is the (n + 1)st Baxter number. Finally, partitions a rectangle into two rectangles. tation #RP we define a new class of permutations, so-called quasiSee Figure 5 for examples of guillotine and nonmonotone permutations, and extend the previous result guillotine partitions. In this section we consider the for this type of permutations. number of guillotine partitions. It is easy to see that this number depends only on the number of points in 5.1 Generating p oint-constrained partitions. P . Let GP(n) be the number of guillotine partitions In this section we define two operators that enable us when |P | = n. We derive a recursive formula for GP(n) to explore the space of all the partitions. Given a par- by assuming that the leftmost vertical segment that cuts tition x we can get new partitions by applying each of R goes through the k th point (left to right) in P , then the following operators on x. summing up over all possible values of k , and finally by multiplying by 2 (for the symmetric partitions in which Definition 5.1. Let p be a point in P , and suppose R is cut by at least one horizontal segment): the segment s that passes through p is horizontal. The G operator Flip(x, p) changes the orientation of s to P(n - 1) + (5.2) GP(n) = 2 vertical, while extending the segments supported by s (that is, one of whose endpoints is contained by s) until , G kn 1 each one of these segments reaches a horizontal segment GP(k - 1) P(n - k ) 2 or the bounding rectangle. Flipping a vertical segment =2 is defined in a similar way. where GP(0) = 1. This formula is equivalent to a recursive formula of the nth Schr¨der number: o Definition 5.2. Suppose t is an endpoint of a segment n-1 k s1 , that lies on another segment s2 . The operator S (k )S (n - 1 - k ), S (0) = 1 Rotate(x, t) extends s1 beyond t until it reaches another (5.3) S (n) = S (n - 1) + =0 segment (or the boundary), and shrinks s2 to t (deleting the portion of s2 that does not contain the point of P ) Thus we have: while extending the segments that were supported by the shrunk part (in order to maintain a valid partition). Theorem 5.1. Given a rectangle R which encloses a Figure 6: Applying the Flip and Rotate operators See Figure 6 for examples of the Flip and Rotate operators. Given a rectangle R which encloses a set of points P , we denote by G(R, P ) = (V , E ) the directed graph of partitions of (R, P ), where V ={x : x is a partition of (R, P )} and E ={(x1 , x2 ) : x2 is reachable from x1 by a single Flip or Rotate operation}. Lemma 5.1. G(R, P ) is connected. set P of n noncorectilinear points, the number of guillotine partitions of (R, P ) is the nth Schr¨der number. o 5.3 Partitions and p ermutations. Definition 5.4. Given a set P of noncorectilinear points, we refer to the relative order of the points in P as the permutation of P and denote it by (P ). Representing the relative order of the points by a permutation = (1 , 2 , 3 , . . . , n ) is feasible since the Proof. Let x1 and x2 be two distinct partitions, and points are noncorectilinear. By i = j we mean that let xv be the partition in which all the segments are the ith point along the x-axis is the j th point along vertical. The partition xv can be reached from both x1 the y -axis. It is easy to see that given two pairs of a and x2 by a series of at most n Flip operations, where rectangle and a set of points, (R1 , P1 ) and (R2 , P2 ), such n is the size of P . Note that every Flip operation is that |P1 | = |P2 | and (P1 ) = (P2 ), we always have reversible by a single Flip operation on the same point, #RP c (R1 , P1 ) = #RP c (R2 , P2 ). In other words, the and a series of Rotate operations. Thus, there is a path number of partitions depends only on the permutation from x1 to x2 (through xv ) in G(R, P ). of points and neither on the bounding rectangle nor on 740 pn+1 pn+1 pn+1 2 2 p1 p1 p1 1 1 (a) An additional point (b) Set a vertical segment (c) Extend the vertical segment Figure 7: From Tn (i, j + k ) to Tn+1 (i + 1, j + 1) the actual point coordinates. Therefore, we will also use the notation #RP c ( ). However, experiments we have performed showed that when (P1 ) = (P2 ) it is possible to have #RP c (P1 ) = #RP c (P2 ). For example, #RP c (1, 2, 3, 4) = 92 while #RP c (3, 1, 4, 2) = 93. 5.4 The numb er of partitions of identity p ermutations. Lemma 5.2. Let In be the identity permutation on n. #RP c (In ) = B (n + 1). Proof. Given a partition x we denote by bottom(x) (resp., top(x) ) the set of vertical segments touching the bottom (resp., top) edge of the bounding rectangle R. Similarly, left(x) (resp., right(x) ) denote the set of horizontal segments touching the respective edges of R. Let Tn (i, j ) be the number of different partitions of n points with the identity permutation, such that for every partition x, |top(x)| = i and |right(x)| = j . Then we can write the following recurrence relation for n 0: (5.4) , k T Tn+1 (i + 1, j + 1) = n (i, j + k ) + Tn (i + k , j ) =1 (a) 2 concatenated above 1 2 (b) Partitions of 1 and 2 2 1 1 (c) One combination of the partitions of 1 and 2 (d) Another combination of the partitions of 1 and 2 Figure 8: Partitions of a quasi-monotone permutation of n points as described above, and there are no two different partitions x1 , x2 of n points, that lead to the same partition of n + 1 points. Therefore, i (5.5) #RP c (In ) = Tn (i, j ), ,j 0 which is exactly B (n + 1) [4]. 5.5 Quasi-monotone p ermutations and their numb er of partitions. In this section we first define quasi-monotone permutations and explore some of their properties. Then we show that the number of partitions for a quasi-monotone permutation is B (n + 1). where T0 (0, 0) = 1 and Tn (i, j ) = 0 for n < 0. To understand why this relation holds, note that we can create a partition x of n + 1 points such that |top(x)| = i + 1 and |right(x)| = j + 1 from a partition x of n points, such that |top(x )| = i and |right(x )| = j + k (for k 1), by: 1. Adding an additional point pn+1 to the right and above all the points of x ; 2. Setting a vertical segment sn+1 through pn+1 ; and 5.5.1 Quasi-monotone p ermutations. Let 1 = (1 , 2 , 3 , . . . , n ) and 2 = (1 , 2 , 3 , . . . , m ) be two permutations on n and m, respectively. We say that = (1 , 2 , 3 , . . . , n+m ) is the result of concatenating 2 above 1 if i = i for 1 i n and n+i = n + i for 1 i m (see Figure 8(a)). Likewise, we say that = (1 , 2 , 3 , . . . , n+m ) is the result of concatenating 2 below 1 if i = m + i for 1 i n and n+i = i for 1 i m. 3. Extending sn+1 downwards using Rotate operations until k - 1 segments are removed from Definition 5.5. is a quasi-monotone permutation if right(x). 1. = (1); or 2. There are two quasi-monotone permutations 1 and Figure 7 shows these steps. We can create in a similar 2 such that is the result of concatenating 2 way a partition x of n + 1 points, for which |top(x)| = o above or below 1 . i + 1 and |right(x)| = j + 1, from a partition x f ) n points, such that |top(x | = i + k (for k 1) A similar definition was suggested by Shapiro and and |right(x )| = j , by passing a horizontal segment Stephens [18] in their analysis of matrices that eventuthrough a new point pn+1 . Clearly, every partition ally fill up under bootstrap percolation. The following x of n + 1 points can be created from a partition x followsfrom their results: 741 Observation 5.1. The number of quasi-monotone per- reflect a with respect to the x-axis we get a partition mutations of length n is the (n - 1)st Schr¨der number. a of n points in the reverse identity permutation, such o that F (a ) = (l, b, r, t). The corollary follows directly They also showed that the portion of quasi-monotone from this fact and from Proposition 5.1. permutations (out of all permutations) approaches zero as n tends to infinity. Lemma 5.3. Let be a quasi-monotone permutation Another characterization of quasi-monotone permu- of n points. For every interface F , #RP c ( , F ) = tations is in terms of forbidden subsequences. A per- #RP c (In , F ). mutation = (1 , 2 , 3 , . . . , n ) Sn avoids a certain subpermutation Sk (for k n) if it does not contain Proof. By induction on n. For n = 1 a permutation a subsequence (i1 , i2 , . . . , ik ) with the same pairwise of one point is both the identity permutation and comparisons as . The set of permutations of length quasi-monotone permutation. Assume the claim is n avoiding is denoted by Sn ( ). It can be shown true for every quasi-monotone permutation of n < n that the set of quasi-monotone permutations is equal to points, and let be a quasi-monotone permutation of Sn (3142, 2413), suggesting an alternative proof [20] that n points. The permutation may be a concatenationtheir number is the (n - 1)st Schr¨der number. o above or a concatenation-below of two quasi-monotone permutations. 5.5.2 The numb er of partitions for quasiSuppose that is the result of concatenating a monotone p ermutations. In this section we prove quasi-monotone permutation 2 Sn-k above another that the number of partitions when the points are in quasi-monotone permutation 1 Sk . Then all the a quasi-monotone permutation is B (n + 1). partitions of can be created by considering every Let x be a partition. The interface of x, denoted pair of a partition of 1 and a partition of 2 , and by F (x), is an ordered quadruple (l, t, r, b), such that by "combining" every such pair in all the possible l = |left(x)|, t = |top(x)|, r = |right(x)|, and b = combinations (see Figure 8). Note that given x1 and |bottom(x)|. We denote by #RP c ( , F ) the number x2 , partitions of 1 and 2 , respectively, the number of partitions with permutation and interface F . of partitions of that are created by combining x1 and x2 in all the possible combinations depends only Proposition 5.1. For every n, l, t, r, b, on F (x1 ) and F (x2 ). Moreover, the interface of every #RP c (In , (l, t, r, b)) = #RP c (In , (l, b, r, t)). such combined partition also depends only on F (x1 ) and F (x2 ) and the way they were combined. Note that this property is not intuitive and does not According to the induction hypothesis, for every follow from simple symmetry arguments. In this short pair of interfaces F and F we have #RP c ( , F ) = 1 2 1 1 version of the paper we only provide a brief sketch of #RP c (I , F ) and #RP c ( , F ) = #RP c (I k 1 2 2 n-k , F2 ). the proof. All the partitions of In can be created by combining all Proof. We prove this proposition by showing a one-to- the pairs of a partition of Ik and a partition of In-k in one mapping, , such that for every partition x of n all possible combinations. Again, the number of combipoints in the identity permutation and with the interface nations and the interface of every such combined parti(l, t, r, b), (x) is a partition of n points in the identity tion depends only on the interfaces of the partitions of permutation, and F ( (x)) = (l, b, r, t). The mapping Ik and In-k , and on the way they were combined. Thus, is defined recursively: If x contains a guillotine cut, then for every concatenation-above cquasi-monotone permuc (x) is the result of applying on the partitions induced tation and interface F , #RP ( , F ) = #RP (In , F ). Suppose now that is the result of concatenatby that cut (if the cut is horizontal, then reflection about ing a quasi-monotone permutation 2 Sn-k below the ascending diagonal is required before applying on the subproblems, and reflection about the descending another quasi-monotone permutation 1 Sk . It fol1 p diagonal is required afterwards). Otherwise, we find lows from Corollary 5.c that for every c air of interfaces F1 and F2 , #RP (Ik , F1 ) = #RP (I k , F1 ) and two segments (after reflection if needed), s1 top(x) c c and s2 bottom(x), such that s1 is to the left of s2 . #RP (In-k , F2 ) = #RP (I n-k , F2 ). Using the induci We use these segments as `pseudo' guillotine cuts and tion hypothesis we concludecthat for every pac r of two interfaces F1 and F2 , #RP (1 , F1 ) = #RP (I k , F1 ) apply on the subproblems they induce. and #RP c (2 , F2 ) = #RP c (I n-k , F2 ). Then, acCorollary 5.1. Let I n be the reverse identity per- cording to the combination arguments given above mutation on n (n, n - 1, . . . , 3, 2, 1), then for every and by using Corollary 5.1, for every concatenationn, l, t, r, b, #RP c (In , (l, t, r, b)) = #RP c (I n , (l, t, r, b)). below quasi-monotone permutation and interface F , #RP c ( , F ) = #RP c (I n , F ) = #RP c (In , F ). Proof. Let a be a partition of n points in the identity In conclusion, the claim holds for all quasipermutation, such that F (a) = (l, t, r, b). When we monotone permutations. 742 Theorem 5.2. Given a rectangle R which encloses a set P of n noncorectilinear points, such that (P ) is a quasi-monotone permutation on n, #RP c (R, P ) = B (n + 1). Proof. The claim follows from lemmata 5.2 and 5.3. that: (1) Every vertex vi V has a label `vertical' or `horizontal,' according to the orientation of si ; and (2) There is an edge from vi to vj labeled `left' (resp., `below') if si sj (resp., si b sj ). Using the concept of a partition graph it is possible to define two point-free partitions as equivalent if 6 Point-Free and Point-Constrained Partitions their partition graphs are isomorphic. We proceed by In this section we establish a relation between point-free mentioning some properties of partition graphs. partitions and point-constrained partitions. First, we Property 6.1. Given a partition r, G(r) is a tournapresent a new representation of a point-free partition-- ment. the partition graph. Then, we use this representation to describe the relation between point-free and point- Proof. (sketch) This property can be proven by induction on n and considering the partition we get by removconstrained partitions. ing either the lowest segment in left(r) or the leftmost segment in bottom(r) (the one whose endpoint lies on 6.1 The partition graph the other is removed). Definition 6.1. Given a (point-free) partition we deNote that since a partition graph is also transitive fine two partial orders of the segments in the partition. We say that segment s1 is left of segment s2 , denoted (this follows from Definition 6.1(4)), it must be acyclic (even when the labels on the edges are ignored). Thus, s1 s2 , if: 1. s1 is vertical, s2 is horizontal, and s1 contains the any partition graph defines a total order of its vertices. left endpoint of s2 ; or The next observation follows from this fact and from 2. s1 is horizontal, s2 is vertical, and s2 contains the Observation 6.1. right endpoint of s1 ; or 3. s1 and s2 are vertical, 1 is the line supporting s1 , Observation 6.2. Given a partition r, let si be a s2 is to the right of 1, and the projection of s2 on vertical (resp., horizontal) segment, and let v1 < v2 < · · · < vn be the total order of the vertices of G(r). 1 contains more than one point of s1 ; or b 4. There is a segment s {s1 , s2 } such that s1 / s (vi < vj if there is an edge vi vj .) Let vj vi and a l r vk vi (resp., vj vi and vk vi ) be the vertices that and s s2 . correspond to sb and sa (resp., sl and sr ). Then j is i i i i In a similar manner we define the relation below below the maximal index such that there is an edge vj vi between two segments s1 and s2 , and denote it by lef t s1 b s2 . (resp., vj vi ), and k is the minimal index such that ef We show below that the union of and b is a there is an edge v below v (resp., v lt v ). i k i k total relation on any set of segments defining a valid partition. Lemma 6.1. Suppose G(V , E ) is a partition graph, and Let s be a horizontal segment. We denote by sl and let v1 < v2 < · · · < vn be the total order of V . Then the sr the vertical segments that bound s from left and from graph induced by v2 , v3 , . . . , vn is also a partition graph. right, respectively. Similarly, for a vertical segment s, we denote by sb and sa the horizontal segments that Proof. Let r be a partition whose partition graph is bound s from below and from above, respectively. The G, and let s1 be the segment in r that corresponds to next observation follows from Definition 6.1 and will be v1 . s1 must be the lowest segment in left(r) or the leftmost segment in bottom(r). Removing s1 from r useful later on: while extending the segments that have their bottom Observation 6.1. Let s be a horizontal segment and endpoint (in the first case) or their left endpoint (in the let x = s be another segment. If s x then either second case) on s1 , towards the bounding rectangle, will x = sr or sr x. If x s then either x = sl or result in a valid partition whose corresponding graph is x sl . We can derive a similar observation about the subgraph of G induced by v2 , v3 , . . . , vn . vertical segments and the `below' relation. We can argue the same about the subgraph induced Using the `left' and `below' relations, we can now by v1 , v2 , . . . , vn-1 . Thus: define the "partition graph." Corollary 6.1. Suppose G(V , E ) is a partition graph, Definition 6.2. Given a partition r of a rectangle by let v1 < v2 < · · · < vn be the total order of V , i