The automorphism group of the complete binary rooted tree of height $3$ Can someone give me some help with this problem:
How do I find the automorphism group of the complete binary rooted tree of height $3$ ($15$ vertices)?
when an automorphism $F$ on a graph $G=(V,E)$ is defined as follows:
$\{v,u\}$ is an edge in $E$ iff $\{F(v),F(u)\}$ is an edge in $F(E)$.
I tried to start counting the permutations, but it seems there is a different and better way to approach the problem.
 A: Let $G_n$ denote the automorphism group of the complete binary rooted tree of height $n$.  So, $G_1 \cong C_2$, the cyclic group of order $2$.
What about height $2$?  You have automorphisms switching one pair of leaves on the left and the other pair on the right (in the usual planar picture of the rooted tree).  Call these $a_1$ and $a_2$.  Together they generate a subgroup of $G_2$ that is isomorphic to $C_2 \times C_2$, the Klein $4$ group.  There is an additional automorphism generator, say $b$ that exchanges the left and right branches at the root.  $G_2 \cong \langle a_1, a_2, b \rangle$.  In fact the subgroup $\langle a_1, a_2 \rangle$ is normal in $G_2$, and
$$
G_2 \cong (C_2 \times C_2) \rtimes C_2.
$$
This construction is called a wreath product and can be written
$$
C_2 \wr C_2.
$$

Now, for height $3$ (and beyond), we iterate the construction.  There are two isomorphic copies of $G_2$ in $G_3$ generated by the subtrees on either side of the root.  The direct product of these two generate a normal subgroup inside of $G_3$, permuted by one additional generator at the root.  So,
$$
\begin{align}
G_3 &\cong (G_2 \times G_2) \rtimes C_2 \\
&\cong \bigg( \big( (C_2 \times C_2) \rtimes C_2 \big) \times \big( (C_2 \times C_2) \rtimes C_2 \big) \bigg) \rtimes C_2,
\end{align}
$$
a group of order $2^7 = 128$, generated by $7$ involutions.
In other words, $G_3$ is an iterated wreath product:
$$
G_3 \cong G_2 \wr C_2 \cong \big( C_2 \wr C_2 \big) \wr C_2.
$$

Beyond $n = 3$, we have the recursive formula
$$
G_{n + 1} \cong G_n \wr C_2 \cong \big( G_n \times G_n \big) \rtimes C_2,
$$
which gives the recurrence relation for the orders of the automorphism groups:
$$
\big| G_{n + 1} \big| = 2\big| G_n \big|^2.
$$
Together with the base case $\big| G_1 \big| = 2$, the can be solved to show that
$$
\big| G_n \big| = 2^{2^n - 1}.
$$
