3
$\begingroup$

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                     
   |                      |                        
   *                      *                         
  / \                     |                      
 *   *                    *                      
                          |  
                          *
$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Lets say I want to do this for a graph with an extra vertice attached to 4. I have 6 total ways to swap nodes , 2 ways to rotate, and one way to do nothing for total of 9, which makes no sense. Could you give an example for another one as well please? $\endgroup$ Jun 14, 2017 at 0:28
  • 1
    $\begingroup$ @LegionDaeth I've added two examples as well as the specific case you mentioned. $\endgroup$ Jun 14, 2017 at 1:03
  • $\begingroup$ You might want to add a note that 2 and 2' relates to the first tree in my question for anyone else that reads this. Brilliant answer though, bravo. $\endgroup$ Jun 14, 2017 at 1:15
  • $\begingroup$ @LegionDaeth I wrote "This is the same picture as the first tree but with n−1 vertices attached to the centre rather than 3." Do you think that could be made clearer? $\endgroup$ Jun 14, 2017 at 1:18
  • $\begingroup$ Missed that when I skimmed over it a second time so I figured another reader might make the same mistake. Nevermind, if they care enough they'll read the comments or read more closely. $\endgroup$ Jun 14, 2017 at 1:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .