The [Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number) $C\_n$ count both 


1. the Dyck paths of length $2n$, and
2. the ways to associate $n$ repeated applications of a binary operation.


We call the latter *magma expressions*; we will explain below.


**Dyck paths, and their lattice structure**


A *Dyck path of length $2n$* is a sequence of $n$ up-and-right strokes and $n$ down-and-right strokes, all having equal length, such that the sequence begins and ends on the same horizontal line and never passes below it. A picture of the five length-6 Dyck paths is shown here:



```
A:          B:          C:          D:          E:
    /\
   /  \        /\/\        /\            /\
  /    \      /    \      /  \/\      /\/  \      /\/\/\

```

There is an order relation on the set of length-$2n$ Dyck paths: $P\leq Q$ if $P$ fits completely under $Q$; I'll call it the *height order*, though in the title of the post, I called it "Dyck order". I've been told it should be called the Stanley lattice order. For $n=3$ it gives the following lattice:



```
   A
   |
   B
  / \
 C   D
  \ /
   E

```

For any $n$, one obtains a poset structure on the set of length-$2n$ Dyck paths using height order, and in fact this poset is always a Heyting algebra (it represents the subobject classifier for the topos of presheaves on the twisted arrow category of $\mathbb{N}$, the free monoid on one generator; see [this mathoverflow question](https://mathoverflow.net/questions/272394/reference-request-heyting-algebra-structure-on-catalan-numbers)).


**Magma expressions and the "exponential evaluation order"**


A set with a binary operation, say •, is called a [magma](https://ncatlab.org/nlab/show/magma). By a *magma expression of length $n$*, we mean a way to associate $n$ repeated applications of the operation. Here are the five magma expressions of length 3:



```
A:            B:             C:             D:             E:
  a•(b•(c•d))   a•((b•c)•d)    (a•b)•(c•d)    (a•(b•c))•d    ((a•b)•c)•d

```

It is well-known that the set of length-$n$ magma expressions has the same cardinality as the set of length-$2n$ Dyck paths: they are representations of the $n$th Catalan number.


An [ordered magma](http://www.labri.fr/perso/courcell/Textes/BC-Raoult%281980%29.pdf) is a magma whose underlying set is equipped with a partial order, and whose operation preserves the order in both variables. Given an ordered magma $(A,$•$,\leq)$, and magma expressions $E(a\_1,\ldots,a\_n)$ and $F(a\_1,\ldots,a\_n)$, write $E\leq F$ if the inequality holds for every choice of $a\_1,\ldots,a\_n\in A$. Call this the *evaluation order*.


Let $P=\mathbb{N}\_{\geq 2}$ be the set of natural numbers with cardinality at least 2, the *logarithmically positive* natural numbers. Equipped with the operation given by exponentiation, $c$•$d\:=c^d$, we obtain an ordered magma, using the usual $\leq$-order. Indeed, if $2\leq a\leq b$ and $2\leq c\leq d$ then $a^c\leq b^d$.


**Question:** Is the exponential evaluation order on length-$n$ expressions in the ordered magma $(P,$^$,\leq)$ isomorphic to the height order on length-$2n$ Dyck paths?


I know of no *a priori* reason to think the answer to the above question should be affirmative. A categorical approach might be to think of the elements of $P$ as sets with two special elements, and use them to define injective functions between Hom-sets, e.g. a map
$$\mathsf{Hom}(c,\mathsf{Hom}(b,a))\to\mathsf{Hom}(\mathsf{Hom}(c,b),a).$$
However, while I can define the above map, I'm not sure how to generalize it. And the converse, that being comparable in the exponential evaluation order means that one can define a single injective map between hom-sets, is not obvious to me at all.


However, despite the fact that I don't know where to look for a proof, I do have evidence to present in favor of an affirmative answer to the above question.


**Evidence that the orders agree**


It is easy to check that for $n=3$, these two orders do agree:



```
            a^(b^(c^d))                     A := A(a,b,c,d)
                 |                          |
            a^((b^c)^d)                     B
            /         \                    / \
 (a^b)^(c^d)           (a^(b^c))^d        C   D
            \         /                    \ /
            ((a^b)^c)^d                     E

```

This can be seen by taking logs of each expression. (To see that C and D are incomparable: use a=b=c=2 and d=large to obtain C>D; and use a=b=d=2 and c=large to obtain D>C.) Thus the evaluation order on length-3 expressions in $(P,$^$,\leq)$ agrees with the height order on length $6$ Dyck paths.


(Note that the answer to the question would be negative if we were to use $\mathbb{N}$ or $\mathbb{N}\_{\geq 1}$ rather than $P=\mathbb{N}\_{\geq2}$ as in the stated question. Indeed, with $a=c=d=2$ and $b=1$, we would have $A(a,b,c,d)=2\leq 16=E(a,b,c,d)$.)


It is even easier to see that the orders agree in the case of $n=0,1$, each of which has only one element, and the case of $n=2$, where the order $(a^b)^c\leq a^{(b^c)}$ not-too-surprisingly matches that of length-4 Dyck paths:



```
             /\ 
 /\/\   ≤   /  \

```

Indeed, the order-isomorphism for $n=2$ is not too surprising because there are only two possible partial orders on a set with two elements. However, according to [the OEIS](https://oeis.org/A000112), there are 1338193159771 different partial orders on a set with $C\_4=14$ elements. So it would certainly be surprising if the evaluation order for length-4 expressions in $(P,$^$,\leq)$ were to match the height order for length-8 Dyck paths. But after some tedious calculations, I have convinced myself that these two orders in fact *do agree* for $n=4$! Of course, this could just be a coincidence, but it is certainly a striking one.


**Thoughts?**



Is the order on repeated exponentiation the Dyck order?
**EDIT:** I can complete half of the proof, showing that the magma order refines the Dyck order.




---


Following Martin Rubey's comment, there is a standard bijection between association orders and Dyck paths that uses [reverse Polish notation](https://en.wikipedia.org/wiki/Reverse_Polish_notation) (RPN). For $n=3$, the five association orders, when written in RPN, are



```

a b c d ^ ^ ^
a b c ^ d ^ ^
a b ^ c d ^ ^
a b c ^ ^ d ^
a b ^ c ^ d ^

```

If we ignore the initial `a` and interpret letters as up strokes and carets as down strokes then we get Dyck paths. The Dyck order is generated by the operation "replace `x ^` with `^ x`" (where `x` is any letter). So proving your claim reduces to showing that


1. if you replace `x ^` with `^ x` then the value of the entire expression decreases, for all choices of values (from $\mathbb{N}\_{\ge2}$) of the variables; and
2. if you have a pair of RPN expressions such that you cannot get from one to the other by a sequence of such replacements, then you can get either expression to be larger than the other by suitably choosing values (from $\mathbb{N}\_{\ge2}$) for the variables.


To prove part 1, note first that in a fixed RPN expression, weakly increasing the value of any variable causes
the overall value to weakly increase, by the ordered magma property.


Now consider two valid RPN expressions $\alpha$ and $\beta$ that differ only in that at one point,
$\alpha$ has `x ^` while $\beta$ has `^ x`.
Just after completing this part of the calculation, stack $\alpha$ will have $A,B^C$ on top
while stack $\beta$ will have $A^B,C$ on top, for some $A$, $B$, and $C$ in $\mathbb{N}\_{\ge2}$.
If we continue the calculation until just before the first caret that affects $A$ in stack $\alpha$
(equivalently, until the first caret that affects $A^B$ in stack $\beta$),
then the top of stack $\alpha$ will look like $A, B^{CD}$ (followed by a caret)
while the top of stack $\beta$ will look like $A^B, C^D$ (followed by a caret)
for some $D$ (possibly equal to 1, in the case where said caret shows up immediately).
Applying the caret then yields $A^{B^{CD}}$ on stack $\alpha$
and $A^{BC^D}$ on stack $\beta$. But 
$B^{CD} = (B^C)^D \ge (BC)^D \ge (B^{1/D}C)^D = BC^D$ for all $B, C \in\mathbb{N}\_{\ge2}$ and $D\ge1$.
So the value on stack $\alpha$ at this stage is $\ge$ the value on stack $\beta$.
Since the remainder of the computation is the same for both stacks, the eventual value of $\alpha$
will be $\ge$ the eventual value of $\beta$.


It seems very likely to me that we can prove part 2 by finding a place $P$ where Dyck path 1 exceeds Dyck path 2
and another place $Q$ where Dyck path 2 exceeds Dyck path 1, and inserting an extremely large number at one of
these points to force whichever expression we want to be larger. But I haven't quite figured out how to
say this rigorously.


