Number of different colourings of nodes Consider a tree where each node has 2 subnodes, with a total of 7 nodes. So the maximum level of the tree is 2. Each node can be coloured white or black. Two colourings are equivalent if the one is about to enter in another by changing the left and right subtrees.
What is the corresponding permutation group? And what is the total number of different colourings?
Now I want to solve this with the theory of Polya. But I don't even know which permutation group belongs to this problem. Any help is appreciated.
 A: Your tree looks like
   1
  / \
 2   3
/ \ / \
4 5 6 7

and the relevant permutation group for the Pólya counting theorem is the group of permutations where we say "two colorings are equivalent if they are related by one of these permutations".
So in this case the relevant permutions are those that interchange the left and right subtress of one of the inner nodes, that is,
$$\begin{align} x &= (23)(46)(57) & \text{(swap children of 1)} \\
y &= (45) &\text{(swap children of 2)} \\
z &= (67) &\text{(swap children of 3)} \end{align}$$
and all permutations that can be written as products of these.
So the first step is to figure out which croup these $x$, $y$, and $z$ generate. You could do that simply by computing all of the possible products of group elements until you don't find any more, but it is quicker to go about it algebraically and observe that the relations
$$ x^2=y^2=z^2=e \qquad yx = xz \qquad zx = xy \qquad zy=yz $$
(which are easy to check) imply that every element in the group can be written as
$$ x^iy^jz^k \qquad i,j,k\in\{0,1\} $$
So there are 8 elements that you can enumerate in a systematic way and then apply Pólya's theorem.
A: Counting without Pólya
I think this is easier than using the Pólya theorem for this particular question: Let $a_n$ be the number of different colorings of a tree with $n$ levels. (So concretely you're looking for $a_3$).
Clearly we have $a_1=2$.
For $a_{n+1}$ we can choose the color of the root node in $2$ ways. For each of these ways the subtrees can either be equivalent (in $a_n$ ways) or different (in $\binom{a_n}2=\frac{a_n(a_n-1)}2$ ways). So we have
$$ a_{n+1} = 2\left(a_n+\frac{a_n(a_n-1)}2\right) = a_n(a_n+1) $$
Then finding $a_3$ is just a matter of applying this recurrence twice:
$$\begin{align} a_1 &= 2 \\ a_2 &= 2\cdot 3 = 6 \\ a_3 &= 6 \cdot 7 = 42 \end{align} $$
These numbers form sequence A007018 in the Online Encyclopedia of Integer Sequences, which gives a number of other combinatorial meanings for them.
