User:Antti Karttunen/Notes on the orbits of A074679-A074680

(Almost ready, but not quite...)

Definition of automorphisms A074679 & A074680

Catalan bijection (or automorphism) *A074679 is defined to act on binary trees on the following way:

$\longrightarrow$

Rotate binary tree left, if possible.

$\longrightarrow$

Otherwise, swap its sides.

In this notation, $a$, $b$ and $c$ refer to arbitrary subtrees sprouting from the marked vertices. They could be empty trees or trees of any finite size. The $\mathbf {0}$ means that, by implication, there is an empty tree at that vertex, i.e. that the vertex is a leaf. It should be clear that the above definition produces a bijection, as

• neither of the above operations will change the total size of a binary tree,
• the set of non-empty binary trees is partitioned to two disjoint subsets by their domains:
  • those trees where the right-hand-side subtree is not empty, and
  • those trees where the it is empty.
• their ranges are also disjoint:
  • those trees where the left-hand-side subtree is not empty, and
  • those trees where it is empty.

Furthermore, we adopt the convention that an empty tree is always silently mapped to itself. And clearly, the inverse automorphism (*A074680) is given by:

$\longrightarrow$

Rotate binary tree right, if possible.

$\longrightarrow$

Otherwise, swap its sides.

Note that the above definitions work equally well for both unlabeled and labeled rooted plane binary trees. Moreover, instead of thinking the latter operation of *A074679 as exchanging the sides tête-à-tête, we can think that the empty right hand side (a leaf node) is passed beneath the root to the left side, and the old left hand side tree makes room for it, by itself moving to the right hand side.

Example of automorphisms' action on the binary trees of four internal vertices

Proposition

The number of distinct orbits of binary trees of $n$ internal vertices (including root), into which they are partitioned by automorphisms *A074679 and *A074680 is given by A001683(n+1), i.e. the same sequence as for Catalan automorphisms *A057161 & *A057162, but shifted once right.

The proof is as follows.

Let's look first how automorphisms *A057161 & *A057162, which by definition rotate Eulerian polygon triangulations, affect the corresponding trivalent plane trees and binary trees, into which the polygon triangulations are mapped to:

Definition: Boron trees

A 3-valent tree or boron tree for short, is a non-planar, non-rooted tree where all the internal nodes have valency 3. I.e. it is a binary tree where neither the orientation nor the position of the root has been fixed. (That is, there is no "root").

The sequence A000672 gives the number of such trees with $n$ (unlabeled) leaves.

Definition: Cameron's quaternary relation

Cameron introduced a quaternary relation for the leaves of trees. The relation $ab|cd$ when restricted to the boron trees is true for any given four distinct leaves $a,b,c$ and $d$ of a tree, if, after discarding all the other nodes and edges of the tree other than those lying on paths joining these four leaves, as well as suppressing all the divalent nodes on those paths, the result is of the following form:

Cameron notes that with boron trees, any four leaves, in some order, satisfy the relation.

Definition: unlabeled plane trivalent tree (flexagons)

An unlabeled plane trivalent tree is a planar, non-rooted tree where all the internal nodes have valency 3. I.e. it is a binary tree where the orientation of the tree has been fixed, but not the position of root. The sequence A001683 gives the number of such trees with $n$ (unlabeled) leaves, or equivalently, with $n-2$ internal nodes.

Note that a boron tree can be mapped to a plane trivalent tree by fixing a circular order on its leaves.

Lemma 1

When acting on the binary trees with labeled leaves, the automorphisms *A074679 and *A074680 preserve the circular order of leaves (when the root node is counted as an internal node, not as a leaf).

Proof. The binary tree rotation will not change the circular order of leaves. On the other hand, if *A074679 does swap instead of rotation, then it will effectively rotate the last leaf (in depth-first wise order) to the front of the other leaves, which also keeps the circular order intact.

Lemma 2

When acting on the binary trees with labeled leaves, the automorphisms *A074679 and *A074680 preserve the Cameron's quaternary relation (when the root node is counted as an internal node, not as a leaf).

Proof. It is clear that swapping one leaf to the other side does not change the quaternary relation of any four leaves. For binary tree rotation, we see that both trees:

and

when they are series-reduced, map to one and same Plane Boron Tree:

where again, the labels $a$, $b$ and $c$ refer to arbitrary subtrees sprouting from those vertices. Thus, neither the binary tree rotation will change the quaternary relations between any vertices of the tree, and thus both *A074679 and its inverse *A074680 preserve the equivalence class of trivalent plane trees ... Blaa blaa...

Thus *A074679 preserves the equivalence class of the trivalent plane trees to which a binary tree is mapped to when it's series-reduced (and the position of its root is forgotten in that process). However, we still have to prove that there is one-to-one correspondence between the trivalent plane trees and the orbits of *A074679, i.e. that the said equivalence classes are never partitioned into two or more disjoint cycles by *A074679.

The following two lemmas are precisely for that.

Lemma 3

Given any finite binary tree, one or more successive applications of automorphism *A074679 will eventually swap its left and right hand side as:

$\rightarrow \cdots \rightarrow$

The proof is by induction over the size of the right-hand-side tree. For the trees of the form there is nothing to prove, as the lemma is immediately satisfied (this is our base case), so let's concentrate on those trees where the right hand side is not empty, but instead of the form , so that the whole tree is of the form . As our induction hypothesis, we assume that both

$\rightarrow \cdots \rightarrow$ and $\rightarrow \cdots \rightarrow$

hold, which taken together, imply that

$\rightarrow \cdots \rightarrow$

holds as well. Here $\longrightarrow$ means one application, and $\rightarrow \cdots \rightarrow$ one or more applications of automorphism *A074679.

To see how this works, let's proceed step by step: Automorphism *A074679 first rotates the tree left as:

$\longrightarrow$

Now, by the first part of the induction hypothesis given above, we assume that one or more further applications of *A074679 will eventually swap left and right hand side of the produced tree, thus giving us:

$\rightarrow \cdots \rightarrow$

This in turn rotates to the left as:

$\longrightarrow$

Now, by the second part of the induction hypothesis, we assume that one or more further applications of *A074679 will eventually swap the left and right hand side of the produced tree giving:

$\rightarrow \cdots \rightarrow$

which in turn, is rotated to the left as:

$\longrightarrow$

and we have indeed obtained a binary tree, where original tree's () left and right hand side have been exchanged. This proves the induction hypothesis and the whole lemma.

Why this works? The size of the right hand side tree is waxing and waning at every step with each successive application of *A074679, and although it in many cases will grow larger than the original right hand side tree (), we see that we need to pay attention/stipulate about the size of rhs tree only at the points (2) and (4), where the subtrees $R^{R}$ and $R^{L}$ are guaranteed to be smaller than itself. These in turn decompose respectively as $R^{R^{R}}$ & $R^{R^{L}}$ and $R^{L^{R}}$ & $R^{L^{L}}$, etc., each branch further decomposing to the left and right hand side, as far as empty trees (leaves) are reached in any branch, which are then handled by the base case. Specifically, no leaf of the original left hand side tree, $L$, will pass underneath the root, before we have reached the last step in the above process, where $L$ is finally on the right hand side alone.

Lemma 4

As a corollary of the previous lemma, we have:

Every leaf of a labeled finite binary tree will visit the position of the right child of the root node at some point on the orbit to which automorphism *A074679 sends the said tree.

Proof: from the steps (2) and (4) of the detailed proof of the previous lemma, we see that the successive applications of *A074679 will bring every leaf of the right hand side tree eventually to the right child of the root, before they are swapped (passed underneath the root) to be the left child of the root. After the fifth (the final step), the original left side tree, $L$, has transmigrated to be the new right hand side tree, and all its leaves will in turn have the same fate.