Some equivalence relation from flipping binary trees

Question

I know almost nothing in combinatorics, so this question might be very easy, or well-known.

Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between the root (some fixed vertex of valency $1$), leaves (vertices of valency $1$ that are not the root) and internal vertices (vertices of valency $3$).

On these trees we can define the following operations. For any internal vertex $v$ of a tree $T$ we can flip the two branches growing up from $v$ as it is shown on the picture:

Then we say two trees $T_1$ and $T_2$ are equivalent if one can be obtained from the other by some combination of the operations described above.

So my question is: how can we describe the set of equivalences classes? I would be happy with the answer of the type: we can (easily) encode trees into some "data", and then each equivalence class is represented by the "data" that satisfies some conditions. Here "data" is maybe a sequence of numbers, or something else (I don't know combinatorics, so I don't know what are the efficient tools to deal with this kind of problem).

Thank you very much for your help!

Answer 1

You are looking for a canonical rooted tree representation. One such representation can be given as follows (Aho, Hopcroft, Ullman):

data Tree = Leaf | Node Tree Tree

canonical_name Leaf = "ab"
canonical_name (Node left_subtree right_subtree) = 
  let left_name = canonical_name left_subtree in
  let right_name = canonical_name right_subtree in
  if left_name < right_name then "a" + left_name + right_name + "b"
  else "a" + right_name + left_name + "b"

I hope this helps $\ddot\smile$

Answer 2

To help you learn more about this class of trees note that they have the ordinary generating function $T(z)$ with the functional equation (where $[z^n] T(z)$ counts the equivalence classes on $n$ nodes) $$T(z) = 1 + \frac{1}{2} z T(z)^2 + \frac{1}{2} z T(z^2).$$ by the Polya enumeration theorem applied to $D_2,$ whose cycle index is $\frac{1}{2}(q_1^2+q_2).$

Enter this equation into your favorite CAS to obtain the following sequence: $$1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, \ldots$$

This is enough data to consult the OEIS, where we find that these are the so-called Wedderburn-Etherington numbers.

Knowing that, we can in turn consult the MathWorld entry, which has some nice pictures. Enjoy!

The Maple code for the initial segment of the functional equation is this:

T_approx := q -> add(a[k]*z^k, k=0..q);

r := 1 + 1/2*z*T_approx(15)^2 + 1/2*z*subs(z=z^2, T_approx(15));
r_ex := expand(r):
eqs := {seq(coeff(r_ex, z, k) = a[k], k=0..15)}:

solve(%);
subs(%, [seq(a[k], k=0..15)]);

Addendum 2015-02-16. A much more efficient computation is given by the recurrence relation $$t_n = \frac{1}{2}\sum_{q=0}^{n-1} t_q t_{n-1-q} + [[n-1\equiv 0\bmod 2]]\frac{1}{2} t_{(n-1)/2}$$ where we have used the Iverson bracket and $t_0 = 1.$