Noncrossing Partitions Under Rotation and Reflection

DAVID CALLAN LEN SMILEY Department of Statistics Department of Mathematical Sciences University of Wisconsin-Madison University of Alaska Anchorage 1300 University Ave 3211 Providence Drive Madison, WI 53706-1532 Anchorage AK 99508 callan(at)stat.wisc.edu smiley(at)math.uaa.alaska.edu

October 18, 2005

Abstract

We consider noncrossing partitions of [n] under the action of (i) the reflection group (of order 2), (ii) the rotation group (cyclic of order n) and (iii) the rotation/reflection group (dihedral of order 2n). First, we exhibit a bijection from rotation classes to bicolored plane trees on n edges, and consider its implications. Then we count noncrossing partitions of [n] invariant under reflection and show that, somewhat surprisingly, they are equinumerous with rotation classes invariant under reflection. The proof uses a pretty involution originating in work of Germain Kreweras. We conjecture that the “equinumerous” result also holds for arbitrary partitions of [n].

1 Introduction

A noncrossing partition of [n] = {1, 2, …, n} is one for which no quadruple a < b < c < d has a, c in one block and b, d in another. This implies that if the elements of [n] are situated around a circle with 1 → 2 → 3 → ⋯ → n → 1 forming a cycle, and neighboring elements within each block are joined by line segments, then no line segments cross one another (see figure below).

The map i ↦ i + 1 (mod n) on [n] induces a map—the rotation operator R—on partitions π of [n]. Equivalence under repeated application of R divides them into rotation classes: A(π) = {R^{i}(π)}_{i≥1}. The complement of a partition π of [n] is C(π) := n + 1 − π (elementwise). It is easy to check that C ∘ R = R^{−1} ∘ C and so the complement operation permutes rotation classes. We say a partition π is self-complementary if C(π) = π and a rotation class A is self-complementary if C(A) = A. As we will see, a self-complementary rotation class need not contain any self-complementary partitions.

The operations rotation and complementation both preserve the noncrossing (NC) property of partitions. In particular, a rotation class consists entirely of NC partitions if it contains a single one. A NC rotation class may be represented by a polygon diagram with the labels removed, we’ll call it an NC Polygon (or Partition) Pattern (NCPP).

•  •^{1}  ^{2}_{3}_{4}^{5}  ^{6}

polygon diagram of the NC partition polygon diagram of its rotation class 134-2-56: labels fixed in place is an NCPP: no labels, rotate at will

Clearly, a NC partition is self-complementary if its labeled polygon diagram is invariant when flipped across a vertical line, and a NC rotation class is self-complementary if its plane polygon pattern is achiral, that is, invariant when flipped over (across any line).

A bicolored plane tree is a plane tree (no root, no labels) in which each vertex is colored white or yellow (say) in such a way that adjacent vertices get different colors. The color of one vertex determines that of all the others (see Figure 5). We exhibit a bijection from NC rotation classes (n points) to bicolored plane trees (n edges) in §2. We count self-complementary NC partitions in §3 and show they are equinumerous with self-complementary NC rotation classes, equivalently, achiral NC polygon diagrams in §4. Remarks, figures, and a conjecture comprise §5. The Appendix contains enumerations and tables. The enumeration of bicolored plane trees (A054357) has been significantly generalized in [2]. We note that (scaled) Shabat polynomials [1, 4] are also counted by A054357.

2 Bijection

The bijection from NC polygon diagrams to bicolored binary trees is depicted in the Figure below. In forming the polygon diagram of a NC partition, the convex hull of each block of size k forms a k-sided yellow polygon even for k = 1, 2 by liberal interpretation of “polygon” as illustrated. The polygons are disjoint because the partition is noncrossing. Ignoring the labels and considering the configuration of polygons only up to rotation, it represents an NC polygon pattern (NCPP).

3 2 1 10 9 8 7 6 5 4 An NC polygon diagram with superimposed bicolored plane tree polygon sides ↔ tree edges

The bijection is clear: place a vertex in each region of the circle, both yellow and white. Join vertices in adjacent regions by edges. Then allow each vertex to inherit the color of the region it’s in to get the desired bicolored plane tree. As for invertibility, the “star” tree with yellow leaves joined to a white center corresponds to the NCPP all of whose polygons are of the degenerate one-sided type. Otherwise the tree has a non-leaf yellow vertex and its inverse is formed recursively as illustrated below.

T_{1}  T_{2} T_{3} T_{4}

the polygon surrounding an internal yellow vertex; recursively construct polygons for the trees T_{i} on their corresponding arcs

There are two immediate consequences of this bijection.

• The Catalan numbers (A000108) count bicolored plane trees with a distinguished edge. This is because the positioning of the labels on the circle can be captured by associating an edge in the tree with label 1, say the first tree edge encountered travelling clockwise from 1 around the polygon incident with 1. Thus the distinguished-edge bicolored plane trees on n edges are in correspondence with ordinary NC partitions of [n], counted by C_{n} [11].

• On NC partitions, as well as on circular NC partitions, the statistics “# singletons” and “# adjacencies” have the same distribution, in fact a symmetric joint distribution. This is due to the correspondences yellow leaf ↔ singleton block, and white leaf ↔ adjacency, that is, two consecutive elements of [n] in the same block. (Of course consecutive is taken here in the circular sense, so n and 1 are considered consecutive.) The symmetry of the joint distribution holds for unrestricted partitions too [5].

3 Counting self-complementary NC partitions

Using paths from (0, 0) with Upsteps (1, 1) and Downsteps (1, −1) (see, e.g., [6]), we will show that the number of self-complementary NC partitions of [n] is \binom{n}{⌊n/2⌋}. There is a bijection from Dyck n-paths (Quadrant 1, ending at (2n, 0)) to NC partitions of [n] that sends # peaks to # blocks. Given a Dyck n-path, number its upsteps left to right and then give each downstep the number of its matching upstep. The numbers on each descent (maximal sequence of contiguous downsteps) form the blocks of the corresponding NC partition.

. [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] ........................................................................................................................^{1  4  5 3  8 7  9 6 2  11  12 10}^{1}  ^{2}  ^{3}  ^{4}  ^{5}  ^{6}  ^{7}  ^{8}  ^{9}  ^{10} ^{11}  ^{12}_{number downsteps,}_{each with the number of its matching upstep}_{•}  ^{•}  _{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  _{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  _{•}

Partition downstep labels by descents to get

1 − 4 − 5 3 − 8 7 − 9 6 2 − 11 − 12 10,

a noncrossing partition with arc diagram

1  2  3  4  5  6  7  8  9  10 11 12

Under this bijection, peak downsteps correspond to largest block elements, and downsteps returning the path to ground level correspond to smallest elements in maximal blocks (a maximal block is one whose arcs would get wet if it rained, here there are 3 such: 1, 2 6 9, 10 12).

Theorem 1. The number of self-complementary NC partitions of [n] is |A_{n}| = \binom{n}{⌊n/2⌋}.

Proof We give a bijective proof for n even. (The case n odd is similar and is omitted.) So suppose n = 2m. The right hand side clearly counts paths of m upsteps and m downsteps (balanced m-paths). Now a NC partition π of [2m] induces a partition τ of [m] by intersecting its blocks with [m]. For τ_{i} a block of τ, set \overline{τ_{i}} = 2m + 1 − τ (elementwise). If π is self-complementary then so is τ and each block of π has one of the three forms τ_{i}, \overline{τ_{i}} or τ_{i} ∪ \overline{τ_{i}} for some block τ_{i} of τ. The first two forms come in complementary pairs, the last form is permissible only if τ_{i} is a maximal block of τ (else π would have a crossing). So self-complementary NC partitions π of [2m] correspond to NC partitions τ of [m] in which each maximal block may (or not) be marked: a mark on τ_{i} indicating that τ_{i} ∪ \overline{τ_{i}} is a block in π, the absence of a mark indicating that τ_{i}, \overline{τ_{i}} are separate blocks of π. Using the NC partition ↔ Dyck path correspondence above, these marked objects correspond in turn to Dyck m-paths with returns (to ground level) available for marking. Returns split a Dyck path into its components (Dyck subpaths whose only return is at the end). Flip over each component that terminates at a marked return to obtain a balanced m-path. This is the desired bijection from self-complementary NC partitions of [2m] to balanced m-paths.

4 Counting achiral NC Polygon Patterns

Theorem 2. The set A_{n} of achiral NC Polygon Patterns (or self-complementary NC rotation classes) of [n] is equinumerous with the set of self-complementary NC partitions of [n], and hence |A_{n}| = \binom{n}{⌊n/2⌋}.

To prove this, recall two related operations on NC partitions [7, 10] defined using polygon diagrams as illustrated in Figures 1,2,3 below.

In each case, new vertices (in blue) interleave the old vertices (in black) but their labelings differ. The new labels are then formed into maximal blocks subject only to: new polygons are disjoint from the old ones.

It is clear from their defining diagrams that

H^{2} = R^{−1}, T^{2} = I, T = CH

and it is not hard to see that T R = R^{−1}T and hence, by induction, T R^{i} = R^{−i}T for all i. The following result is key to the bijection establishing the Theorem.

Proposition 1. CT=TRC

Proof H^{2} = R^{−1} ⇒ H = R^{−1}H^{−1} ⇒ CT = R^{−1}T C = T RC.

For n ≥ 3, H ≠ R and we note in passing that the operations C, T, H, R on NC partitions of [n] generate a dihedral group D_{2n} (of 4n elements) with presentation ⟨H, C : H^{2n} = C^{2} = I, CHC^{−1} = H^{−1}⟩.

Figure 1: NC partition π by polygons Figure 2: π with H(π)

Figure 3: π with T (π)

Next we define the notion of complement order on partitions in achiral NC rotation classes. Suppose A ∈ A_{n} and π is a partition in A. Then C(π) ∈ A (because A is achiral) and so C(π) = R^{i}(π) for some i ≥ 1 (i = n will do if C(π) = π). Define the complement order of π to be the minimal such i ≥ 1.

Lemma 1. (i ) An achiral rotation class A contains at most 2 self-complementary partitions. (ii ) If |A| is odd, then A contains exactly one self-complementary partition. (iii ) If |A| is even, then either every partition in A has even complement order or every partition in A has odd complement order. In the former case, A contains 2 selfcomplementary partitions; in the latter case, none.

The proof is deferred. Theorem 2 will follow from this lemma if we can show that, among even-cardinality achiral NC rotation classes A in A_{n}, there are just as many associated with even complement order as with odd. (Of course, |A| even implies n even.) We claim the transpose T is a bijection, indeed an involution, that interchanges these two families. To see this, first suppose that A ∈ A_{n} has even cardinality, say |A| = 2s, and π ∈ A has even complement order, say C(π) = R^{2m}π. Then, using Proposition 1,

C(T π) = T R Cπ = T R^{2m+1}π = R^{−(2m+1)}T π = R^{2s−2m−1}(T π)

and T π has odd complement order. The other direction is similar, the desired bijection is established, and Theorem 2 follows.

Proof of Lemma 1 Suppose a rotation class A contains a self-complementary partition π. Then the complement of every other element of A is given by

CR^{i}π = R^{−i}Cπ = R^{−i}π  (1)

Now suppose R^{i}π ∈ A is also self-complementary. It follows from (1) that R^{2i}π = π. Set t = |A| so that R^{j}π = π ⇒ t | j. Hence t | 2i.

If t is odd, then t | i and R^{i}π = π, implying that π is the only self-complementary partition in A. If t is even, say t = 2s, then s | i and R^{i}π is one of R^{s}π and R^{2s}π = π. These facts establish part (i) and the “at most one” half of part (ii).

For the “at least one” half of part (ii), suppose |A| is odd. Take π ∈ A. Since A is achiral, Cπ = R^{k}π for some k and so the complement of each element of A is given by CR^{i}π = R^{k−i}π. If k is even, then i = k/2 makes R^{i}π self-complementary. On the other hand, if k is odd, say k = 2ℓ + 1 and |A| = 2s + 1, then i = ℓ − s makes R^{i}π self-complementary. This establishes part (ii).

For part (iii), let t := |A| be even. First, suppose some π ∈ A has even complementary order k: C(π) = R^{k}π. Then C(R^{i}π) = R^{k−i}π = R^{k−2i}R^{i}π and the powers of R that fix R^{i}π are all ≡ k − 2i (mod t) and hence even. Thus every element of A has even complementary order and R^{i}π is self-complementary for i = k/2 and i = (k + t)/2. Similarly, if some element π of A has odd complementary order, then they all do, and the equation C(R^{i}π) = R^{i}π has no solution.

5 Concluding Remarks

1. The transpose defined in Figure 3 above coincides with the restriction to NC partitions of the conjugate [5] defined on all partitions of [n]. In particular, the algorithmic definition of conjugate given in [5] provides a practical way to compute the transpose.

2. An analog of Theorem 2 appears to hold for arbitrary partitions: the number of self-complementary rotation classes of partitions on [n] coincides with the number of self-complementary partitions of [n]. The proof of Lemma 1 goes through unchanged (it does not use the NC property). Unfortunately, the conjugate does not serve in the role of transpose to interchange the two relevant families in this larger setting, and it would be interesting to find an extension of the transpose that does.

3. Figures 4 and 5 show the 28 bijective pairs (by geographic position) of NCPP’s and bicolored plane trees for n = 6. To avoid clutter, only one leaf per tree displays its color. Singleton (yellow) leaves are colored “0”; adjacency (white) leaves are colored “1”.

Figure 4: NC Patterns, n=6

Figure 5: Bicolored 6-edge plane trees

Appendix: Enumeration Formula for Unlabeled NC Partitions and Bicolored Plane Trees (almost ab initio)

The partitions of the set [n] = {1, 2, …, n} (the decompositions of [n] as a union of pairwise-disjoint, non-empty subsets) are counted by the sequence of Bell numbers. If the elements of [n] are regarded as the set of labels of n otherwise indistinguishable objects, the unlabeled enumeration of partitions of these objects is the same as counting the partitions of the integer n.

Non-crossing partitions (cf. Introduction) are beautiful, and have been closely studied. Motzkin noted [8, last sentence] that the number of labeled non-crossing partitions, as a function of n, satisfies the Catalan recurrence, and in fact these are counted by the sequence of Catalan numbers.

In the unlabeled case, there are two candidate sequences: the leading one regards the circle as embedded in a plane with the points evenly spaced and counts non-crossing partitions inequivalent under rotations of the circle (these are the NC Partition Patterns); the second identifies two partition classes counted in the first which are the same after reflection across a diameter of the circle (we might call these classes chirally inequivalent NC Partition Patterns). Motzkin [8, penultimate sentence] gave the beginning of the latter sequence as 1, 2, 3, 6, 9, 24. This contains an (almost certainly clerical) error: the value for n = 5 should be 10, not 9.

Because the “label/unlabel” paradigm has been invoked, the sequence NCP P (n) fits into one of at least two competing enumerative analogies: if the circle is discarded entirely, then Bell numbers : partitions of n :: Catalan numbers : NCP P (n); if only the NC requirement is relaxed, then Bell : possibly crossing partition patterns (A084423) :: Catalan : NCP P (n).

The essential fact needed in the direct enumeration of NC partition patterns was proven by V. Reiner [9]: if n = kd, k ≥ 2, and the points are labelled a_{1}, a_{2}, …, a_{n}, then the number of NC partitions having the property “a_{i} and a_{j} are in the same part if and only if a_{i+d (mod n)} and a_{j+d (mod n)} are in the same part” is \binom{2d}{d}. We refer to such NC partitions as d-clickable (suggested by analogy to clicking a physical dial with n positions through d positions and arriving at the same partition). Reiner gives two proofs; for the convenience of the reader we informally describe the bijection used in one of them. Using k distinct colors for the a’s, relabel the points consecutively to make k monocolor intervals subscripted 1, …, d. Consider the ’unwrapped’ doubly-infinite sequence

… a_{d−1}, a_{d}, a_{1}, a_{2}, …, a_{d}, A_{1}, …, A_{d}, a_{1}, a_{2} . . . . . . . . . , a_{d−1}, a_{d}, a_{1}, …

(here font/case is used to denote color). On the circle, find a part of the partition, say of size p, consisting entirely of a consecutive set of points. This will always be possible for an NC partition. In a set L place the subscript of the first (clockwise) element in the chosen part, and in a set R the subscript of the last. This will be possible if the part is proper. Remove all elements with subscripts equal to those in this part from the doubly-infinite sequence and from the circle. The resulting sequence still consists of equal length monocolor intervals in the k colors, and (after equispacing the remaining points on the circle) is (d − p)-clickable. Repeat the process until no such proper part remains to be chosen, at which time the sets L and R are equinumerous, but otherwise arbitrary, subsets of [d]. The number of ways of specifying such an L and R is easily seen to be \binom{2d}{d}.

To reverse the process, consider a copy of the original doubly-infinite sequence and for each element of L (resp. R) place a Left (resp. Right) parenthesis to the left (resp. right) of each symbol in the sequence with subscript equal to this element. When L and R are exhausted the partition may be decoded from the parenthesized string in the usual manner.

Figure 6 displays a partition of [24] which is 3-, 6-, and 12-clickable (we use partitioning walls instead of polygons for viewability). The generator (click) σ of ℤ_{24} may be thought of as a rotation of the diagram through 2π/24 leaving the labels in place. The pictured partition is then a fixed point of σ^{3i}, i = 0, …, 7. As one of the \binom{6}{3} 3-clickables, it is a fixed point of all of these, including σ^{3}, σ^{9}, σ^{15}, and σ^{21}. As one of the superset of \binom{12}{6} 6-clickables, (cf Figure 7), it may not be invariant under those 4 rotations, but it must be a fixed point of σ^{6}, and σ^{18}, while as one of the \binom{24}{12} 12-clickables, it need only be an invariant of {σ^{12}, σ^{0}}. These considerations generalize succinctly in the following enumeration.

Figure 6: A 3-clickable partition Figure 7: A 6-clickable partition, not 3-clickable

Theorem 3. The number of NC Partition Patterns of n points on a circle is

\frac{1}{n}(\frac{1}{n + 1}\binom{2n}{n} + ∑_{\begin{matrix}1≤i<n \\ i|n \end{matrix}} ϕ(\frac{n}{i})\binom{2i}{i})

.

Proof The Cauchy-Frobenius principle for the rotation group of order n counts our equivalence classes by summing over all group elements the number of objects (labelled NC partitions) invariant under the element, then dividing by the group order. The identity element accounts for the Catalan number as the left summand. It is easily verified that those non-identity group elements which fix all i-clickable partitions but not all j-clickable partitions for j > i are exactly those of order \frac{n}{i}, and these number ϕ(\frac{n}{i}). This gives the right summand, using the result of V. Reiner.

As shown in Section 4, the central binomial coefficient counts those NC Partition Patterns invariant by any reflection across a diameter which fixes the n points. Cauchy-Frobenius allows us to count chirally inequivalent patterns by adding half the noninvariant patterns to the invariant ones.

The enumeration of bicolored plane trees predates, and thus confirms, Theorem 3. The number of (free) plane trees on n edges is known to be

FPT(n) := \frac{1}{2n} ∑_{d|n} ϕ(\frac{n}{d})\binom{2d}{d} − \frac{(C_{n} − C_{\frac{n−1}{2}} )}{2},

see (A002995). Here and below C_{m} is understood to be 0 if m is not an integer, and the term involving Catalan numbers is an integer because C_{m} is odd iff the integer m has the form 2^{k} − 1.

The size of a plane tree is its number of edges. The subtrees of a vertex are the plane trees obtained by deleting the vertex and its incident edges. A center of a plane tree is a vertex v that minimizes max{size(T) : T a subtree of v}. A plane tree either has a unique center or two adjacent centers. Deleting the connecting edge in the latter case leaves two ordered trees. Symmetry then implies that the number of bicolored plane tree on n edges is 2 FPT(n) − C_{\frac{n−1}{2}} (A054357), since ordered trees are yet another manifestation of the Catalan numbers. Clearly this agrees with the Cauchy-Frobenius count of NC partition patterns above.

Michel Bousquet applied Cauchy-Frobenius (“Lemme de Burnside”) to enumerate mary cacti in [3], applying a scheme due to Liskovets. His result includes bicolored plane trees as a special case.

n NC Rotation Classes NC Dihedral Classes NC Chiral patterns ÷2
or NCPP’s  (chiral equivalence)
A054357  (A054357+A001405)/2 (A054357-A001405)/2
1  1  1  0
2  2  2  0
3  3  3  0
4  6  6  0
5  10  10  0
6  28  24  4
7  63  49  14
8  190  130  60
9  546  336  210
10  1708  980  728
11  5346  2904  2442
12  17428  9176  8252
13  57148  29432  27716
14  191280  97356  93924
15  646363  326399  319964
16  2210670  1111770  1098900
17  7626166  3825238  3800928
18  26538292  13293456  13244836
19  93013854  46553116  46460738
20  328215300  164200028  164015272
21  1165060668  582706692  582353976
22  4158330416  2079517924  2078812492

References

[1] N. Adrianov and A.Zvonkin, Composition of plane trees, Acta Applicandae Mathematicae 52, Numbers 1-3, July 1998, 239–245.

[2] Miklos Bona, Michel Bousquet, Gilbert Labelle and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22–56.

[3] Michel Bousquet, Quelques rsultats sur les cactus planaires, Annales des Sciences Mathematiques du Quebec, 24 (2000) No. 2. p. 107-128.

[4] Mireille  Bousquet-Mélou,  Combinatorics  in  Bordeaux,

www.mat.univie.ac.at/ slc/wpapers/s34bordeaux des.PS.

[5] David Callan, On conjugates for integer compositions and set partitions, preprint, http://front.math.ucdavis.edu/math.CO/0508052 .

[6] Emeric Deutsch, Dyck Path Enumeration, Discrete Math. 204 (1999), 167–202.

[7] Germain Kreweras, Sur les partitions non croisees d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350.

[8] Theodore Samuel Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352–360.

[9] Victor Reiner, Noncrossing partitions for classical rotation groups, Discrete Math. 177 (1997), 195–222.

[10] Rodica Simion and Daniel Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), no. 3, 193-206.

[11] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999. Exercise 6.19 and related material on Catalan numbers are available online at http://www-math.mit.edu/ rstan/ec/ .