Recursive Bijections for Catalan Objects

Stefan Forcey Department of Mathematics The University of Akron Akron, OH 44325-4002 USA

                    sf34@uakron.edu

Mohammadmehdi Kafashan and Mehdi Maleki Department of Electrical Engineering The University of Akron Akron, OH 44325-4002 USA

Michael Strayer Department of Mathematics The University of Akron Akron, OH 44325-4002 USA

Abstract

In this note we introduce several instructive examples of bijections found between several different combinatorially defined sequences of sets. Each sequence has cardinalities given by the Catalan numbers. Our results answer some questions posed by R. Stanley in the addendum to his textbook. We actually discuss two types of bijection, one defined recursively and the other defined in a more local, relative, fashion. It is interesting to compare the results of the two.

1 Introduction

1.1 Catalan objects

In the work that led to this note we set out to find explicit bijections between several sequences of sets that are known to be counted by the Catalan numbers, sequence \underline{A000108} in [6]. One sequence of sets we call the right-swept planar unary-binary trees, or right-swept trees for short. These are the same restriction of planar unary-binary trees that are labeled as example “www” in R. Stanley’s Catalan Addendum (version of July 2012) [5]. In [3] Kim describes what we call right-swept trees as a special kind of planar unary-binary trees, and Kim gives in the same article a bijection to the non-crossing partitions. We were inspired to find bijections from these right-swept trees to other familiar sets of objects counted by the Catalan numbers, due to the fact that they have a nice recursive description that is different from the standard Catalan recursion. In this paper we find bijections from the right-swept trees to staircase tilings, planar trees, planar binary trees and arc tree diagrams, allowing the reader to construct many more implied bijections to non-crossing partitions, polygonal dissections and lattice paths. Our first set of recursive bijections is described in Section 2. Our second bijection between staircase tilings and right-swept trees is discussed in Section 3.

A right-swept tree is a rooted planar tree with the following restrictions. In general a node may be a leaf, may have a single child which must be left, middle, or right; or instead may have two children: left and right. Any left child has further restrictions: it may not be a leaf, and it may not have a middle child. Thus any branching to the left is eventually swept right before it can end in a leaf. Figure 1 shows a right-swept tree.

Figure 1: Two views of a right-swept tree. We will use the first, with root at the top. The (remixed) photo is a windswept hawthorne near Galway, original taken by Eoin Gardiner (creative commons).

Our second featured sequence is known as the diagonal rectangular tilings of staircase shapes, or staircase tilings for short. A staircase shape is the outline of a Young diagram corresponding to a partition given by (n, n − 1, …, 1). The Catalan numbers count tilings whose rectangles each include some of the stepped diagonal – i.e., each intersects the end of a row in the Young diagram. These are equivalently described as rectangular tilings of height n staircase shapes that contain exactly n rectangles. The fact that having n rectangles is equivalent to being a diagonal tiling is also true for diagonal rectangulations of the square, and we refer the reader to [4] both for a proof and for some very nice related combinatorics. The staircase tilings are also referred to as tilings of stair-step shapes, as in [2].

There is a well known bijection from staircase tilings to the sets of rooted planar binary trees. Simply removing the “steps,” the vertical and horizontal boundary segments of unit length at the far right and bottom of the figure, and adding a root, yields a binary tree (whose drawing has been rotated from its normal presentation.) A staircase tiling and its corresponding binary tree is shown in Figure 2.

Figure 2: Two views of a staircase tiling. We will use the version on the left. The binary tree in the center is the image of the staircase tiling under the classical bijection: it is formed by removing the steps. We will draw rooted binary trees with the root at the bottom.

The bijection exemplified in Figure 2 is trivially described in recursive terms. A planar binary tree t with more than one leaf (and thus the corresponding staircase tiling) is formed by joining a pair of smaller binary trees–the left and right subtrees whose root is the first branch point of t. Many other Catalan objects have a similar recursive description–triangular dissections of a polygon, bracketings of a string of symbols, and Dyck paths, to name a few. This description leads to Segner’s classic recursion relation for the Catalan numbers c_{n}:

c_{0} = 1 and c_{n+1} = ∑_{k=0}^{n} c_{k}c_{n−k} for n > 0,  (1)

where n is the number of branch points for the binary tree, or the number of rectangles in the staircase tiling. The recursion yields the closed formula:

c_{n} = \frac{1}{n + 1}\binom{2n}{n}.

If X_{n} and X′_{n} are any two of the sequences of sets that have Segner’s recursive description then they are in piecewise bijection (both counted by c_{n}), and the correspondence is explicitly described using the recursion. If a bijection is given between the k^{th} sets of the two sequences, for k = 1 … n, then given an object of X_{n+1} we can decompose it into two objects from earlier in the sequence, find their corresponding objects and use them to construct the corresponding object in X′_{n+1}.

We began by using a different, nonstandard recursion for the Catalan numbers to seek bijections between the staircase tilings and the right-swept trees. Our first bijection discussed in Section 2 is based on an alternate recursive description of the staircase tilings, which fits well with the natural recursive description of the right-swept trees. Here is the recursion that we will be using (its four parts will be explained one at a time in Section 2):

c_{n+1} = c_{n} + c_{n} + (c_{n} − c_{n−1}) + (∑_{k=2}^{n−1} c_{n−k}(c_{k} − c_{k−1})) .

By finding analogous ways to recursively construct other sorts of Catalan objects we can describe them as being in bijection with the right-swept trees, and each other, in new ways. As an example we include non-crossing arc diagrams with distinct left endpoints, or arc trees for short.

Arc trees are defined to be the ways of connecting n + 1 points lying on a horizontal line on the plane with n non-crossing arcs lying above the line such that the left endpoints of the arcs are distinct. There is always a unique series of arcs traveled from left to right from any point to the rightmost point. Thus there is always a unique shortest path to travel from one point to another. These are easily seen to be in bijection with planar rooted trees with n edges, simply by choosing the rightmost point to be the root and then straightening the arcs. See Figure 3.

Figure 3: The bijection from non-crossing arc diagrams with distinct left endpoints to planar rooted trees: from left to right we gradually straighten the arcs. We will draw planar rooted trees with the root at the bottom (as opposed to the right-swept trees with their root at the top.)

2 Recursive bijections

As mentioned, in order to keep this paper self contained, we have repeated the definitions given in R. Stanley’s Catalan addendum (version of 13 July 2012) to [5] of the combinatorial objects www, h^{8}, and h^{5}: called here, respectively, the right-swept trees, staircase tilings and arc trees.

We represent the set of right-swept trees with n nodes as T_{n}, the set of stair-case tilings with n rectangles as S_{n} and the set of arc trees with n arcs as A_{n}. We refer to the sets as the shapes of size n. The five objects for size n = 3 are seen in Figures 4, 5 and 6.

Figure 4: Right-swept trees T_{3}.

Figure 5: Staircase tilings S_{3}.

Figure 6: (Non crossing) arc trees A_{3}.

Here we introduce a recursive method to construct a shape with size of n + 1 in any of these three combinatorial sets using shapes of smaller size. We construct four different types of shapes of size n + 1 using four methods:

1. We define functions f_{R} : X_{n} → X_{n+1}, X ∈ {T, S, A} , n ≥ 1 ∈ ℕ. Depending on which combinatorial object is the input to this function, we perform the following procedures:

a) X = T: In this case, the output in T_{n+1} = f_{R} (T_{n}) is a right-swept tree with n + 1 vertices constructed by adding one vertex to t ∈ T_{n} as the new root whose right child is the root of t. b) X = S: In this case, the output in S_{n+1} = f_{R} (S_{n}) is a staircase tiling with n + 1 rectangles constructed by adding one ((n + 1) × 1) rectangle to the left side of an input from S_{n}.

c) X = A: In this case, the output in A_{n+1} = f_{R} (A_{n}) is is an arc tree with n + 2 points constructed by adding one point to the left side of a ∈ A_{n} and connecting it to the nearest point in a.

Figure 7 represents the operation of f_{R} whose input can be any possible shape with size of n. Thus the number of shapes of size n + 1 which can be constructed by f_{R} is denoted c_{n+1,1} = c_{n}.

Figure 7: Construction of X_{n+1} using f_{R}.

2. We define functions f_{M} : X_{n} → X_{n+1}, X ∈ {T, S, A} , n ∈ ℕ, and for the case n = 0. Depending on which combinatorial object is the input to this function, we perform the following procedures:

a) X = T: In this case, the output in T_{n+1} = f_{M} (T_{n}) is a tree with n + 1 vertices constructed by adding one vertex to t ∈ T_{n} as the new root whose middle child is the root of t. We define T_{0} to be {∅} and define the single element of T_{1} as f_{M}(∅).

b) X = S: In this case, the output in S_{n+1} = f_{M} (S_{n}) is a tiling with n + 1 rectangles constructed by removing the left edge of s ∈ S_{n}, extending s one column to the left and then adding one single square to the bottom of the new column. We define S_{0} to be {∅} and define the single element of S_{1} as f_{M}(∅).

c) X = A: In this case, the output in A_{n+1} = f_{M} (A_{n}) is an arc tree with n + 2 points constructed by adding one point to the left side of a ∈ A_{n} and connecting it to the farthest point in a. We define A_{0} to consist of a single point and define the single element of A_{1} as the image of that point under f_{M}.

Figures 8 and 9 represent the operation of f_{M} whose input can be any possible shape with size of n. Thus the number of shapes of size n + 1 which can be constructed by f_{M} is denoted c_{n+1,2} = c_{n}.

Figure 8: Construction of X_{n+1} using f_{M}.

Figure 9: Examples of the construction of X_{n+1} using f_{M}.

3. We define functions f_{L} : (X_{n} − f_{M}(X_{n−1})) → X_{n+1}, X ∈ {T, S, A} , n ≥ 1 ∈ ℕ. Depending on which combinatorial object is the input to this function, we perform the following procedures:

a) X = T: In this case, the output of f_{L} is a tree with n + 1 vertices constructed by adding one vertex to a size n right-swept tree t as the new root whose left child is the root of t. Here the original root of t will not have a middle child.

b) X = S: In this case, the output of f_{L} is a tiling with n+1 rectangles constructed by adding one ((n + 1) × 1) rectangle to the top of a shape from S_{n}. Here s ∈ S_{n} should not have a single square as its lowest tile. In other words s should not be constructed by f_{M} (S_{n−1}).

c) X = A: In this case, the output of f_{L} is an arc tree with n + 2 points constructed by adding one point to the left side of a size n arc tree a and connecting it to the second nearest point (but not the rightmost one) in a such that the connection does not intersect with any other arc in a. Notice that this is impossible if the input arc tree has an arc between its first and last points. In other words a should not be constructed by f_{M} (A_{n−1}).

Figure 10 represents the operation of f_{L} whose input can be any possible shape with size of n except the shapes constructed by f_{M} (X_{n−1}). Thus the number of shapes of size n + 1 which can be constructed by f_{L} is denoted c_{n+1,3} = c_{n} − c_{n−1}.

Figure 10: Construction of X_{n+1} using f_{L}.

4. For the last case we define functions f : ((X_{n_{1}} − f_{M}(X_{n_{1}−1})) × X_{n_{2}}) → X_{n+1}, X ∈ {T, S, A} , n_{1} > 1 ∈ ℕ, n_{2} ∈ ℕ, n = (n_{1} +n_{2}) ≥ 3. Depending on which combinatorial object is the input to this function, we perform the following procedures:

a) X = T: In this case, the output in T_{n_{1}+n_{2}+1} is a tree with n_{1} + n_{2} + 1 vertices constructed by adding one vertex as the root whose left and right children are the roots of trees from T_{n_{1}} − f_{M}(T_{n_{1}−1}) and T_{n_{2}}, respectively.

b) X = S: In this case, the output in S_{n_{1}+n_{2}+1} is a shape with n_{1} + n_{2} + 1 rectangles constructed by introducing a rectangle of size ((n_{1} + 1) × (n_{2} + 1)) in the top left corner of the shape and adding staircase tilings t_{1} ∈ S_{n_{1}} − f_{M}(S_{n_{1}−1}) and t_{2} ∈ S_{n_{2}} to the bottom and right of the rectangle, respectively. The tiling added to the bottom should not have a single square as its bottom-most tile.

c)X = A: In this case, the output in A_{n_{1}+n_{2}+1} is a shape with points constructed by concatenating arc trees from A_{n_{1}} − f_{M}(A_{n_{1}−1}) and A_{n_{2}} in that order, left to right, by identifying their respective rightmost and leftmost points. Then we add a point to the left side of both and connect it to the identified common point. The input arc tree on the left should not have an arc between its first and last points.

Figure 11 represents the operation of f (., .) to construct a shape of size n_{1} + n_{2} + 1. The first input argument can be any shape with size of n_{1} > 1 except the shapes constructed by f_{M} (X_{n_{1}−1}). However the second argument can be any shape of size n_{2}. The number of shapes of size n + 1 which can be constructed with this function is

denoted c_{n+1,4} = ∑_{k=2}^{n−1} c_{n−k} (c_{k} − c_{k−1}).

Figure 11: Construction of X_{n_{1}+n_{2}+1} using f (X_{n_{1}}, X_{n_{2}})

2.1 Bijections implied by the construction.

The functions we have defined allow the shapes to be built recursively, and to be deconstructed as well. Unique construction and deconstruction allow us to realize a bijection between any two sets whose shapes are built with the four functions defined above. First we note that there is only one element of X_{1} for each of the shapes we consider. Figure 12 shows the three sets of size one.

Definition 1. For n ≥ 1 we define maps α : X_{n} → X′_{n} for X, X′ ∈ {T, S, A} as follows:

For x ∈ X_{n} we consider x to be the shape that results from applying exactly n functions f_{i}, i = 1 … n in a particular order to k initial copies of x_{0} ∈ X_{0}, the single element of size zero for k ≥ 1. Here f_{i} ∈ {f, f_{L}, f_{R}, f_{M}}. We denote as F_{x} the function that is the composition of cartesian products of the n functions f_{i}, whose domain is k copies of X_{0}, and whose sole image is x.

Then α(x) = F_{x}(x′_{0}, x′_{0}, …, x′_{0}) for k copies of x′_{0} ∈ X′_{0}, the element of size zero.

For examples see Figures 13, 15 and 16.

Theorem 2. α : X_{n} → X′_{n} as just defined gives bijections for all X, X′ ∈ {T, S, A}.

Proof. We show that α is well defined, surjective and invertible by demonstrating that for any shape x′ ∈ X′_{n} there is a unique composition of cartesian products of functions from

Figure 12: Trivial bijections between T_{1}, S_{1} and A_{1}. Recall that these are each defined as an image of f_{M}. f_{L}, f_{M}, f_{R} and f that constructs it. Since a given composition constructs only one shape in each of T, S, A, having that composition means having knowledge of a unique shape x ∈ X_{n} corresponding to x′. The existence of a unique composition is argued using strong induction, since the function f takes inputs from sets with smaller indices than just n−1. We note that the single shapes for n = 1 (in Figure 12) are all constructed uniquely by f_{M} by definition. Assuming that shapes smaller than size n are uniquely constructed, we then check for size n as follows:

T : For any right-swept tree t ∈ T_{n}, depending on whether the root has left, middle, right or both left and right children, the tree is uniquely constructed from one or two smaller trees. For the right-swept trees this follows from their definition.

S : For any staircase tiling s ∈ S_{n} the shape is uniquely constructed from one or two smaller shapes. The construction is determined first by whether s has a single square as its bottom-most tile. If that is the case, then s is constructed from a single smaller tiling by f_{M}. Otherwise, we can determine whether it was constructed by f_{L}, f_{R} or f, respectively, by whether s has a a single long rectangle along its top, along its left side, or neither (instead it has a thick rectangle that covers some of both but neither the entire top nor the entire left edges.)

A : For any arc tree a ∈ A_{n} the shape is constructed from one or two smaller shapes. The construction is determined first by whether a has a single arc connecting its first and last points. If that is the case, then a is constructed from a single smaller arc tree by f_{M}. Otherwise, we can determine whether it was constructed by f_{R}, f_{L} or f, respectively, by whether a has a a single short arc connecting its first (leftmost) and second points, a single arc connecting its left-most point with the second available point, or neither (instead it has a single longer arc connecting its left-most point to another, more central, point.)

It is instructive to show that the total number of shapes constructed by our four functions

is equal to c_{n+1}. That is, that the Catalan number c_{n+1} = ∑_{i=1}^{4} c_{n+1,i}. Equivalently we need

to prove that ∑_{k=1}^{n−1} c_{k}c_{n−k} = c_{n+1} − 2c_{n}. To see this we expanded the sum and used Segner’s

recurrence relation for Catalan numbers:

c_{0} = 1 and c_{n+1} = ∑_{k=0}^{n} c_{k}c_{n−k} for n > 0.  (2)

So we have

c_{n+1} = ∑_{k=0}^{n} c_{k}c_{n−k} = c_{0}c_{n} + ∑_{k=1}^{n−1} c_{k}c_{n−k} + c_{n}c_{0} ⇒ ∑_{k=1}^{n−1} c_{k}c_{n−k} = c_{n+1} − 2c_{n}.  (3)

2.2 Examples

Example 1: We want to demonstrate the bijections between right-swept trees, staircase tilings and arc trees for n = 3. For this we use the proposed method twice. So for n = 2 the bijection between these combinatorial objects is illustrated in Figure 13:

Figure 13: Bijections between right-swept trees, staircase tilings and arc trees for n = 2. The top row is formed by f_{M} ∘ f_{M} and the bottom row by f_{R} ∘ f_{M}.

Now the bijections between right-swept trees, staircase tilings and arc trees for n = 3 can be illustrated, in Figure 18:

Example 2: Here we take a shape in S_{12}, seen in Figure 14. We want to find its images under α in T_{12} and A_{12}. First we apply the inverses of our functions introduced before in order to

Figure 14: An example of a staircase tiling with n = 12.

uniquely reduce the size of the shape to n = 1, shown in Figure 15. Now by applying the functions we found in Figure 15, we can construct bijective images of the staircase tiling in the sets of right-swept trees and arc trees, which are shown in Figure 16. Finally we present the induced bijective correspondence for a binary tree with 12 internal nodes and a planar tree with 12 edges. This is seen in Figure 17.

Figure 15: The inverse process on shape of Figure 14. Darkly shaded tiles are discarded by the inverse functions. Thus the tiling x shown here is formed by

F_{x}(x_{0}, x_{0}, x_{0}) = f(f_{M} ∘ f_{L} ∘ f_{R} ∘ f_{M} ∘ f_{M}(x_{0}), f_{R} ∘ f(f_{M}(x_{0}), f_{R} ∘ f_{R} ∘ f_{M}(x_{0}))).

Figure 16: Images (under α) of the shape of Figure 14 in T_{12} and A_{12}

3 Relative bijection from T_{n} to S_{n}

For contrast, we consider a different method for constructing a bijection from right-swept trees to staircase tilings.

We start by describing a second new mapping β : T_{n} → S_{n}. Rather than using recursion, this time we declare several rules about the relative positions of rectangles on one hand and tree nodes on the other. To characterize this mapping, we need several rules which describe how two labeled nodes attached by an edge of the right-swept tree are translated to two labeled rectangles in the staircase tiling.

1. Let two nodes be attached by a tree edge with a positive slope, so that node a is a left child of node b. Then rectangle b will be immediately to the right of rectangle a. See Figure 19.

Figure 17: Corresponding binary tree and planar tree, under bijection induced by α between arc trees and staircase tilings. This example uses the staircase tiling from Figure 14 and Figure 15.

Figure 18: Bijections for n = 3. Each row represents a class of objects mapped to each other, the first three columns by the bijection α and the last two columns via canonical bijections from the staircase tilings and arc trees.

2. For two nodes attached by a negative sloped edge the situation is more complex. If a right child b is the only child of a root, middle child, or right child a, and b itself is a

Figure 19: Example of Rule 1 (β : T_{n} → S_{n}).

leaf or has only a middle or right child, then the rectangle b will be immediately right of the rectangle corresponding to a. See Figure 20.

Figure 20: Example of Rule 2 (β : T_{n} → S_{n}).

3. However, if a right child is produced from a left child (or as part of a left and right child), the corresponding rectangle will be immediately below the rectangle corresponding to the spawning vertex. See Figure 21.

Figure 21: Examples of Rule 3 (β : T_{n} → S_{n}). Rectangles labeled with a letter correspond to that node, as shown by the circles.

4. A middle child b will always correspond to a rectangle directly below the rectangle corresponding to the spawning vertex a. See Figure 22.

Figure 22: Example of Rule 4 (β : T_{n} → S_{n}).

5. There is only one case in which adjacent nodes do not correspond to adjacent rectangles: if b is a right child of a, and b has a left child d. Then rectangle b is right of rectangle a, but Rule 1 is used to place the left child of b (and its left child, etc.) between rectangles a and b. See Figure 23.

Figure 23: Example of Rule 5 (β : T_{n} → S_{n}). The three circled nodes b, d, c all correspond to rectangles right of the rectangle corresponding to a.

This method gives a specific set of instructions at each vertex point for how to proceed with no ambiguity in the decision-making process. Therefore each tree in T_{n} will give a unique structure in S_{n}.

Figure 24 is a final example for the case that n = 10 for the mapping from T_{n} to S_{n}.

Theorem 3. The mapping β : T_{n} → S_{n} determined by the above rules is a bijection.

Proof. We consider the reverse mapping β^{−1} : S_{n} → T_{n}. In a similar fashion, we develop a series of rules for this mapping.

1. If the top-left rectangle goes to the bottom of the figure (i.e., width = 1 unit), the root spawns a right child. If the top-left rectangle goes to the farthest right edge (i.e., depth = 1 unit), the root spawns a middle child. This process is repeated as necessary. See Figure 25.

2. If the top-left rectangle has width greater than 1 unit and depth greater than 1 unit, then a limb of left children is formed where the bottom vertex on this limb corresponds to the left-most rectangle. The length of this limb of left children is determined by the Figure 24: A full example for the case n = 10 (β : T_{n} → S_{n}).

Figure 25: Examples of Rule 1 (β^{−1} : S_{n} → T_{n}).

Figure 26: Example of Rule 2 (β^{−1} : S_{n} → T_{n}).

number of rectangles read from left to right, going as far right as possible. See Figure 26.

3. Any remaining rectangles are treated as right children of the vertex corresponding to the rectangle directly above and the process repeats with these remaining rectangles acting as miniature versions of S_{n}. Notice this rule satisfies the restriction in T_{n} to have a right child or a right and left child following a left child. See Figure 27.

Figure 27: Example of Rule 3 (β^{−1} : S_{n} → T_{n}).

As in the previous case, we now illustrate with a final example, the reverse image for the case n = 10 that we considered earlier. See Figure 28. We use the set of rules developed here, and see that we arrive at the same pre-image in T_{n}.

Figure 28: A full example for the case n = 10 (β^{−1} : S_{n} → T_{n}).

Once again, no ambiguity arises from the rules developed above, and so each output of this algorithm is unique for each unique input.

We now argue that these sets of rules form an inverse function. We define Tier One rules to be Rules 2 and 4 from the former direction and Rule 1 from the latter direction. We define Tier Two rules to be Rules 1 and 5 in the former direction and Rule 2 in the latter direction. We define Tier Three rules to be Rule 3 from the former direction and Rule 3 from the latter direction.

Tier One rules are easily seen to be inverse rules, and when using any Tier One rule from the outset, the resulting figure in the next step is a new tree or staircase shape with n − 1 vertices or rectangles for T_{n} and S_{n}, respectively.

The real key to this process occurs in Tier Two and Tier Three rules. In T_{n}, the Tier Two rules occur any time a left child is introduced, whether it is from the root (Rule 1) or somewhere else in the tree (Rule 5). In S_{n}, the Tier Two rules occur any time a rectangle having width and depth both greater than 1 unit is introduced, either as the top-left rectangle (corresponding to the root in T_{n}) or somewhere else in the staircase (corresponding to a different branch in T_{n}). These two phases are clearly inverses of each other, since Rules 1 and 5 of T_{n} imply Rule 2 of S_{n} and vice versa, and in corresponding sections of the tree and staircase.

Tier Three rules in T_{n} occur whenever a right child branches off of a left limb (where the length of the limb is anywhere from 1 to n − 1 branches). Similarly, Tier Three rules in S_{n} occur any time there are leftover rectangles underneath of a Tier Two structure in S_{n}. In both T_{n} and S_{n}, the process renews itself when Tier Three rules are utilized, leaving smaller tree and staircase structures of corresponding size, both starting independently with the same set of rules the larger structure obeys. Therefore, Tier Three rules in T_{n} imply Tier Three rules in S_{n} and vice verse, and in corresponding sections of the tree and staircase.

Breaking down our algorithm into three tiers of rules has allowed us to show that this function is indeed an inverse function. We therefore have successfully described the bijection between S_{n} and T_{n}.

3.1 Examples contrasting the bijections.

Interestingly, the two bijections α : T_{n} → S_{n} and β : T_{n} → S_{n} set up precisely the same correspondence between right-swept trees and staircase tilings for n = 0, 1, 2. An obvious question is raised: are the two bijections we have described the same? The answer is no. We see this at n = 3, by comparing the tables in Figures 29 and 18.

Figure 29: Bijections for n = 3 for the bijection β. Note that the third and fifth images are switched from those of α in Figure 18.

The slightly larger example we include next in Figure 30 was suggested by an anonymous referee, to whom we owe heartfelt thanks for catching early errors. This example is in n = 5.

Figure 30: Contrasted pre-images of an S_{5} tiling.

Finally we include here in Figure 31 a larger example to highlight the differences. A tree from T_{12} (the same example as in Figure 16) is shown in the center, and then its two images in S_{12}: on the left is the image of the recursive bijection from Section 2 and on the right the image of the relative bijection from Section 3.

Figure 31: Two images of a right-swept tree from T_{12}.

References

[1] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[2] M. Crepinsek and L. Mernik, An efficient representation for solving Catalan number related problems, Int. J. of Pure and Applied Math. 56 (2009), 589–604.

[3] J. S. Kim, Front representation of set partitions, SIAM J. Discrete Math. 25 (2011), 447–461.

[4] S. Law and N. Reading, The Hopf algebra of diagonal rectangulations, J. Combin. Theory Ser. A. 119 (2012), 788–824.

[5] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

2010 Mathematics Subject Classification: Primary 05C05; Secondary 05A19. Keywords: Catalan numbers, bijection, recursion.

(Concerned with sequence \underline{A000108}.)

Received December 1 2012; revised versions received February 24 2013; May 2 2013. Published in Journal of Integer Sequences, May 9 2013.

Return to Journal of Integer Sequences home page.