Number of distinct labelings of a binary tree

Question

I was reading through this article and I noticed that the number of possible labelings for a binary tree seems to be N!. Then I noticed that the unique labelings seems to be half that. This holds true for binary trees like 2, down below, but since I can freely rotate the nodes that are around the central node of 1 I can only find four distinct labelings.

I want to find the number of distinct labelings for a tree, and from my observations N!/2 seems to fit the bill for straight trees, but not for this one. Am I right to assume I can rotate the nodes in such a way that there are only 4 unique labelings for 1? What's the correct formula? Combinations don't seem to work.

   *  1                   *    2                     
   |                      |                        
   *                      *                         
  / \                     |                      
 *   *                    *                      
                          |  
                          *

Answer 1

The correct "formula" is

$$ \text{Number of distinct labellings of } T = \frac{n!}{|\operatorname{Aut}(T)|}. $$

Now what on Earth is $\operatorname{Aut}(T)$? This is the automorphism group of the tree. For example, for the first tree if we switch the two leafs there is no effect. The operation of "swapping the two leafs" and "doing nothing" (the identity function) are automorphisms of the tree.

If we label the tree as

    1
    |
2 - 4 - 3

then we have $6$ possible permutations that keep the tree structure intact. Namely, we can:

• do nothing
• swap $1$ and $2$
• swap $2$ and $3$
• swap $3$ and $1$
• rotate left: $1 \mapsto 2 \mapsto 3 \mapsto 1$
• rotate right: $1 \mapsto 3 \mapsto 2 \mapsto 1$

These 6 operations are the automorphism group of the tree: the entire set of automorphisms. It is a "group" because we can compose two automorphisms by applying one after the other and get a new automorphism. Since there are 6 automorphisms, there are $4!/6 = 4$ distinct labellings.

---

Example 2:

Consider the tree with vertices $1,\dots,n - 1, n$ and edges $1 \sim n$, $2 \sim n$ through $n - 1 \sim n$. This is the same picture as the first tree but with $n - 1$ vertices attached to the centre rather than $3$.

The automorphism group of this tree is the symmetric group $S_{n - 1}$ which consists of all permutations of $1,2,\dots, n - 1$ which are obtained from shuffling the symbols around.

For example with $n - 1 = 7$, I can take the permutation $5137642$ which corresponds to the function that sends $1$ to $5$, $2$ to $1$, $3$ to $3$, $4$ to $7$, $5$ to $6$ and $7$ to $2$.

The symmetric group has $(n - 1)!$ elements (by definition in fact). To see that this number is $(n - 1)(n - 2) \cdots 2 \cdot 1$ notice that there are $n - 1$ ways to pick the first element of the permutation and having done that, there are $n - 2$ ways to pick the second, and so on. Thus there are

$$ \frac{n!}{(n - 1)!} = n $$

distinct ways to label this tree.

---

Example 2': For $n = 5$ above you are looking at all ways to permute $1,2,3,4$. You can

• Swap a pair (6 pairs)
• Swap two pairs (swap a pair then the remaining two vertices, this double counts so you get 6/2 = 3)
• Identity (1)
• Choose three vertices and then rotate among those three (4 choices of three vertices * two directions to rotate = 8)
• 6 more which permute $1,2,3,4$ in a cyclic fashion:
  • $1 \mapsto 2 \mapsto 3 \mapsto 4 \mapsto 1$
  • $1 \mapsto 2 \mapsto 4 \mapsto 3 \mapsto 1$
  • $1 \mapsto 3 \mapsto 2 \mapsto 4 \mapsto 1$
  • $1 \mapsto 3 \mapsto 4 \mapsto 2 \mapsto 1$
  • $1 \mapsto 4 \mapsto 2 \mapsto 3 \mapsto 1$
  • $1 \mapsto 4 \mapsto 3 \mapsto 2 \mapsto 1$

for a total of 6 + 3 + 1 + 8 + 6 = 24

---

Example 3:

Consider the cycle on $n \ge 3$ vertices. This isn't a tree but the same formula applies. The automorphism group here is the dihedral group.

This automorphism group consists of $n$ rotations and $n$ reflections for a total of $2n$ elements (draw this for $n = 3, 4, 5$ to see what's going on). Thus there are

$$ \frac{n!}{2n} = \frac{(n - 1)!}{2} $$

distinct ways to label the cycle graph.