# A self-dual poset on objects counted by the Catalan numbers

## 1 Introduction

There are more than 150 different objects enumerated by Catalan numbers. Two of the most carefully studied ones are noncrossing partitions and 132-avoiding permutations. A partition $`\pi =(\pi _1,\pi _2,\mathrm{},\pi _t)`$ of the set $`[n]=\{1,2,\mathrm{},n\}`$ is called noncrossing  if it has no four elements $`a<b<c<d`$ so that $`a,c\pi _i`$ and $`b,d\pi _j`$ for some distinct $`i`$ and $`j`$. A permutation of $`[n]`$, or, in what follows, an $`n`$-permutation, is called 132-avoiding  if it does not have three entries $`a<b<c`$ so that $`a`$ is the leftmost of them and $`b`$ is the rightmost of them.

Noncrossing partitions of $`[n]`$ have a natural and well studied partial order: the refinement order $`Q_n`$. In this order $`\pi _1<\pi _2`$ if each block of $`\pi _2`$ is the union of some blocks of $`\pi _1`$. The poset $`Q_n`$ is known to be a lattice, and it is graded, rank-symmetric, rank-unimodal, and $`k`$-Sperner . The poset $`Q_n`$ has been proved to be self-dual in two steps , .

In this paper we introduce a new partial order of 132-avoiding $`n`$-permutations which will naturally translate into one of noncrossing partitions. In this poset, for two 132-avoiding $`n`$-permutations $`x`$ and $`y`$, we define $`x<y`$ if the descent set of $`x`$ is contained in that of $`y`$. (We will provide a natural equivalent, definition, too.) We will see that this new partial order $`P_n`$ is a coarsening of the dual of $`Q_n`$. In other words, if for two noncrossing partitions $`\pi _1`$ and $`\pi _2`$ we have $`\pi _1<\pi _2`$ in $`Q_n`$, then we also have $`f(\pi _2)<f(\pi _1)`$ in $`P_n`$, where $`f`$ is a natural bijection from the set of noncrossing partitions onto that of 132-avoiding permutations. This will enable us to prove that $`P_n`$ has the same rank-generating function as $`Q_n`$, and so $`P_n`$ is rank-unimodal, rank-symmetric and $`k`$-Sperner. Furthermore, we will also prove that $`P_n`$ is self-dual in a somewhat more direct way than it is proved for $`Q_n`$.

## 2 Our main results

### 2.1 A bijection and its properties

It is not difficult to find a bijection from the set of noncrossing partitions of $`[n]`$ onto that of 132-avoiding $`n`$-permutations. However, we will exhibit such a bijection here and analyze its structure as it will be our major tool in proving our theorems. To avoid confusion, integers belonging to a partition will be called elements, while integers belonging to a permutation will be called entries. An $`n`$-permutation $`x=x_1x_2\mathrm{}x_n`$ will always be written in the one-line notation, with $`x_i`$ denoting its $`i`$th entry.

Let $`\pi `$ be a noncrossing partition of $`[n]`$. We construct the 132-avoiding permutation $`p=f(\pi )`$ corresponding to it. Let $`k`$ be the largest element of $`\pi `$ which is in the same block of $`\pi `$ as 1. Put the entry $`n`$ of $`p`$ to the $`k`$th position, so $`p_k=n`$. As $`p`$ is to be 132-avoiding, this implies that entries larger than $`nk`$ are on the left of $`n`$ and entries less than or equal to $`nk`$ are on the right of $`n`$ in $`q`$.

Then we continue this procedure recursively. As $`\pi `$ is noncrossing, blocks which contain elements larger than $`k`$ cannot contain elements smaller than $`k`$. Therefore, the restriction of $`\pi `$ to $`\{k+1,k+2,\mathrm{},n\}`$ is a noncrossing partition, and it corresponds to the 132-avoiding permutation of $`\{1,2,\mathrm{}nk\}`$ which is on the left of $`n`$ in $`\pi `$ by this same recursive procedure.

We still need to say what to do with blocks of $`\pi `$ containing elements smaller than or equal to $`k`$. Delete $`k`$, and apply this same procedure for the resulting noncrossing partition on $`k1`$ elements. This way we obtain a 132-avoiding permutation of $`k1`$ elements, and this is what we needed for the part of $`p`$ on the left of $`n`$, that is, for $`\{nk+1,nk+2,\mathrm{},n1\}`$.

So in other words, if $`\pi _1`$ is the restriction of $`\pi `$ into $`[k1]`$ and $`\pi _2`$ is the restriction of $`\pi `$ into $`\{k+1,k+2,\mathrm{},n\}`$, then $`f(\pi )`$ is the concatenation of $`f(\pi _1)`$, $`n`$ and $`f(\pi _2)`$, where $`f(\pi _1)`$ permutes the set $`\{nk+1,nk+2,\mathrm{},n1\}`$ and $`f(\pi _2)`$ permutes the set $`[nk]`$.

To see that this is a bijection note that we can recover the largest element of the block containing the entry 1 from the position of $`n`$ in $`p`$ and then proceed recursively.

###### Example 1

If $`\pi =(\{1,4,6\},\{2,3\},\{5\},\{7,8\})`$, then $`f(\pi )=64573812`$.

###### Example 2

If $`p=(\{1,2,\mathrm{},n\})`$, then $`f(p)=12\mathrm{}n`$.

###### Example 3

If $`p=(\{1\},\{2\},\mathrm{},\{n\})`$, then $`f(p)=n\mathrm{}21`$.

The following definition is widely used in the literature.

###### Definition 1

Let $`p=p_1p_2\mathrm{}p_n`$ be a permutation. We say the $`i`$ is a descent of $`p`$ if $`p_i>p_{i+1}`$. The set of all descents of $`p`$ is called the descent set of $`p`$ and is denoted $`D(p)`$.

Now we are in a position to define the poset $`P_n`$ of 132-avoiding permutations we want to study.

###### Definition 2

Let $`x`$ and $`y`$ be two 132-avoiding $`n`$-permutations. We say that $`x<_Py`$ (or $`x<y`$ in $`P_n`$) if $`D(x)D(y)`$.

Clearly, $`P_n`$ is a poset as inclusion is transitive. It is easy to see that in 132-avoiding permutations, $`i1`$ is a descent if and only if $`p_{i+1}`$ is smaller than every entry on its left, (such an element is called a left-to-right minimum). So $`x<_Py`$ if and only if the set of positions in which $`x`$ has a left-to-right minimum is a proper subset of that of those positions in which $`y`$ has a left-to-right minimum. The Hasse diagram of $`P_4`$ is shown on the Figure below.

Figure 1: The Hasse diagram of $`P_4`$.

The following proposition describes the relation between the blocks of $`x`$ and the descent set of $`f(x)`$.

###### Proposition 1

The bijection $`f`$ has the following property: $`iD(f(x))`$ if and only if $`i+1`$ is the smallest element of its block.

Proof: By induction on $`n`$. For $`n=1`$ and $`n=2`$ the statement is true. Now suppose we know the statement for all positive integers smaller than $`n`$. Then we distinguish two cases:

1. If 1 and $`n`$ are in the same block of $`x`$, then the construction of $`f(x)`$ simply starts by putting the entry $`n`$ to the last slot of $`f(x)`$, then deleting the element $`n`$ from $`x`$. Neither of these steps alters the set of minimal elements of blocks or that of descents in any way. Therefore, the algorithm is reduced to one of size $`n1`$, and the proof follows by induction.
2. If the largest element $`k`$ of the block containing 1 is smaller than $`n`$, then as we have seen above, $`f`$ constructs the images of $`x_1`$ and $`x_2`$ which will be separated by the entry $`n`$. Therefore, by the induction hypothesis, the descents of $`f(x)`$ are given by the minimal elements of the blocks of $`x_1`$ and $`x_2`$, and these are exactly the blocks of $`x`$. There will also be a descent at $`k`$ (as the entry $`n`$ goes to the $`k`$th slot), and that is in accordance with our statement as $`k+1`$ is certainly the smallest element of its block.

$`\mathrm{}`$

We point out that this implies that $`P_n`$ is equivalent to a poset of noncrossing partitions in which $`\pi _1<\pi _2`$ if the set of elements which are minimal in their block in $`\pi _1`$ is contained in that of elements which are minimal in their block in $`\pi _2`$.

### 2.2 Properties of $`P_n`$

Now we can prove the main result of this paper.

###### Theorem 1

The poset $`P_n`$ is coarser than the dual of the poset $`Q_n`$ of noncrossing partitions ordered by refinement. That is, if $`x<y`$ in $`Q_n`$, then $`f(y)<f(x)`$ in $`P_n`$.

Proof: If $`x<y`$, then each block of $`x`$ is a subset of a block of $`y`$. Therefore, if $`z`$ is the minimal element of a block $`B`$ of $`y`$, then it is also the minimal element of the block $`E`$ of $`x`$ containing it as $`EB`$. Therefore, the set of elements which are minimal in their respective blocks in $`x`$ contains that of elements which are minimal in their respective blocks in $`y`$. By Proposition 1 this implies $`D(f(y))D(f(x))`$. $`\mathrm{}`$

Now we apply this result to prove some properties of $`P_n`$. For definitions, see .

###### Theorem 2

The rank generating function of $`P_n`$ is equal to that of $`Q_n`$. In particular, $`P_n`$ is rank-symmetric, rank-unimodal and $`k`$-Sperner.

Proof: By proposition 1, the number of 132-avoiding permutations having $`k`$ descents equals that of noncrossing partitions having $`k`$ blocks, and this is known to be the $`(n,k)`$ Narayana-number $`\frac{1}{n}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left(\genfrac{}{}{0pt}{}{n}{k1}\right)`$. Therefore $`P_n`$ is graded, rank-symmetric and rank-unimodal, and its rank generating function is the same as that of $`Q_n`$, as $`Q_n`$ too is graded by the number of blocks (and is self-dual). As $`P_n`$ is coarser than $`Q_n`$, any antichain of $`P_n`$ is an antichain of $`Q_n`$, and the $`k`$-Sperner property follows. $`\mathrm{}`$

We need more analysis to prove that $`P_n`$ is self-dual, that is, that $`P_n`$ is invariant to “being turned upside down”. Denote $`Perm_n(S)`$ the number of 132-avoiding $`n`$-permutations with descent set $`S`$. The following lemma is the base of our proof of self-duality. For $`S[n1]`$, we define $`\alpha (S)`$ to be the “reverse complement” of $`S`$, that is, $`i\alpha (S)niS`$.

###### Lemma 1

For any $`S[n1]`$, we have $`Perm_n(S)=Perm_n(\alpha (S))`$.

Proof:By induction on $`n`$. For $`n=1,2,3`$ the statement is true. Now suppose we know it for all positive integers smaller than $`n`$. Denote $`t`$ the smallest element of $`S`$.

1. Suppose that $`t>1`$. This means that $`x_1<x_2<\mathrm{}<x_t`$, and that $`x_1,x_2,\mathrm{},x_t`$ are consecutive integers. Indeed, if there were a gap among them, that is, there were an integer $`y`$ so that $`yx_i`$ for $`1it`$, while $`x_1<y<x_t`$, then $`x_1x_ty`$ would be a 132-pattern. So once we know $`x_1`$, we have noly one choice for $`x_2,x_3,\mathrm{},x_t`$. This implies

$$Perm_n(S)=Perm_{n(t1)}(S(t1)),$$
(1)   
where $`S(t1)`$ is the set obtained from $`S`$ by subtracting $`t1`$ from each of its elements.

On the other hand, we have $`nt+1,nt+2,\mathrm{},n1\alpha (S)`$, meaning that $`x_{nt+1}>x_{nt+2}>\mathrm{}>x_n`$, and also, we must have $`(x_{nt+2},\mathrm{},x_n)=(t1,t2,\mathrm{}1)`$, otherwise a 132-pattern is formed. Therefore,

$$Perm_n(\alpha (S))=Perm_{n(t1)}(\alpha (S)|n(t1))$$
(2)   
where $`\alpha (S)|n(t1)`$ is simply $`\alpha (S)`$ without its last $`t1`$ elements. Clearly, $`Perm_{n(t1)}(S(t1))=Perm_{n(t1)}(\alpha (S)|n(t1))`$ by the induction hypothesis, so equations (1) and (2) imply $`Perm_n(S)=Perm_n(\alpha (S))`$.
2. If $`t=1`$, but $`S[n1]`$, then let $`u`$ be the smallest index which is not in $`S`$. Then again, $`x_u`$ must be the smallest positive integer $`a`$ which is larger than $`x_{u1}`$ and is not equal to some $`x_i`$, $`iu1`$, otherwise $`x_{u1}x_ua`$ would be a 132-pattern. So again, we have only one choice for $`x_u`$. On the other hand, the largest index in $`\alpha (S)`$ will be $`n(u1)`$. Then as above, we will only have once choice for $`x_{nu}`$. Now we can delete $`u`$ from $`S`$ and $`nu`$ from $`\alpha (S)`$ and proceed by the induction hypothesis as in the previous case.
3. Finally, if $`S=[n1]`$, then the statement is trivially true as $`Perm_n(S)=Perm_n(\alpha (S))=1.`$

So we have seen that $`Perm_n(S)=Perm_n(\alpha (S))`$ in all cases. $`\mathrm{}`$

Now we are in position to prove our next theorem.

###### Theorem 3

The poset $`P_n`$ is self-dual.

Proof: It is clear that in $`P_n`$ permutations with the same descent set will cover the same elements and they will be covered by the same elements. Therefore, such permutations form orbits of $`Aut(P_n)`$ and they can be permuted among each other arbitrarily by elements of $`Aut(P_n)`$. One can think of $`P_n`$ as a Boolean algebra $`B_{n1}`$ in which some elements have several copies. One natural anti-automorphism of a Boolean-algebra is “reverse complement”, that is, for $`S[n1]`$, $`i\alpha (S)niS`$. To show that $`P_n`$ is self-dual, it is therefore sufficient to show that the corresponding elements appear with the same multiplicities in $`P_n`$. So in other words we must show that there are as many 132-avoiding permutations with descent set $`S`$ as there are with descent set $`\alpha (S)`$. And that has been proved in the Lemma. $`\mathrm{}`$

### 2.3 Further directions

It is natural to ask for what related combinatorial objects we could define such a natural partial order which would turn out to be self-dual and possibly, have some other nice properties. Two-stack sortable permutations  are an obvious candidate. It is known  that there are as many of them with $`k`$ descents as with $`n1k`$ descents, however, the poset obtained by the descent ordering is not self-dual, even for $`n=4`$, so another ordering is needed. Another candidate could be the poset of the recently introduced noncrossing partitions for classical reflection groups , some of which are self-dual in the traditional refinement order.