Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: enter image description here

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!

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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$

share|improve this answer

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)]);
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.