Number of different colourings of nodes

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

I would like to make a first and quite basic contribution using the Polya Enumeration Theorem. This certainly admits improvement, as here we are enumerating all permutations in the cycleindex $Z(Q_n)$ of the permutation group $Q_n$ that permutes the vertices of these rooted full unordered binary trees on $n$ levels. The reader is invited to contribute a cycle index formula that classifies permutations by their cycle structure instead of computing all permutations.

Here are some cycle indices: this is the cycle index for three levels. $$Z(Q_3) = 1/8\,{a_{{1}}}^{7}+1/4\,{a_{{1}}}^{5}a_{{2}} \\+1/8\,{a_{{1}}}^{3}{a_{{2}}}^{2}+1 /4\,a_{{1}}{a_{{2}}}^{3}+1/4\,a_{{1}}a_{{2}}a_{{4}}.$$

This is the index for four levels: $$Z(Q_4) = {\frac {{a_{{1}}}^{15}}{128}}+1/32\,{a_{{1}}}^{13}a_{{2}}+{ \frac {3\,{a_{{1}}}^{11}{a_{{2}}}^{2}}{64}}+1/16\,{a_{{1}}}^ {9}{a_{{2}}}^{3}\\+1/32\,{a_{{1}}}^{9}a_{{2}}a_{{4}}+{\frac {9 \,{a_{{1}}}^{7}{a_{{2}}}^{4}}{128}}+1/16\,{a_{{1}}}^{7}{a_{{ 2}}}^{2}a_{{4}}\\+1/32\,{a_{{1}}}^{5}{a_{{2}}}^{5}+1/32\,{a_{{ 1}}}^{5}{a_{{2}}}^{3}a_{{4}}+1/32\,{a_{{1}}}^{3}{a_{{2}}}^{6 }+1/16\,{a_{{1}}}^{3}{a_{{2}}}^{4}a_{{4}}\\+1/16\,a_{{1}}{a_{{ 2}}}^{7}+1/32\,{a_{{1}}}^{3}{a_{{2}}}^{2}{a_{{4}}}^{2}+1/8\, a_{{1}}{a_{{2}}}^{5}a_{{4}}+1/16\,a_{{1}}{a_{{2}}}^{3}{a_{{4 }}}^{2}\\+1/8\,a_{{1}}a_{{2}}{a_{{4}}}^{3}+1/8\,a_{{1}}a_{{2}} a_{{4}}a_{{8}}.$$

The cycleindex $Z(Q_5)$ can also be computed.
Here is an excerpt: $$\cdots+ {\frac {5\,{a_{{1}}}^{5}{a_{{2}}}^{5}{a_{{4}}}^{4}}{512}}+{\frac {{a_{ {1}}}^{5}{a_{{2}}}^{7}a_{{4}}a_{{8}}}{256}}+{\frac {{a_{{1}}}^{3}{a_{{ 2}}}^{2}{a_{{4}}}^{4}a_{{8}}}{64}}+{\frac {a_{{1}}{a_{{2}}}^{5}{a_{{4} }}^{5}}{64}}\\+1/32\,a_{{1}}a_{{2}}{a_{{4}}}^{3}{a_{{8}}}^{2}+1/32\,a_{{ 1}}{a_{{2}}}^{9}{a_{{4}}}^{3}+1/32\,a_{{1}}{a_{{2}}}^{3}{a_{{4}}}^{4}a _{{8}}+{\frac {{a_{{1}}}^{29}a_{{2}}}{4096}}\\+{\frac {7\,{a_{{1}}}^{27} {a_{{2}}}^{2}}{8192}}+{\frac {{a_{{1}}}^{25}{a_{{2}}}^{3}}{512}}+{ \frac {59\,{a_{{1}}}^{23}{a_{{2}}}^{4}}{16384}}+{\frac {11\,{a_{{1}}}^ {21}{a_{{2}}}^{5}}{2048}}+{\frac {{a_{{1}}}^{25}a_{{2}}a_{{4}}}{4096}} +{\frac {3\,{a_{{1}}}^{23}{a_{{2}}}^{2}a_{{4}}}{2048}}\\+{\frac {15\,{a_ {{1}}}^{21}{a_{{2}}}^{3}a_{{4}}}{4096}}+{\frac {13\,{a_{{1}}}^{19}{a_{ {2}}}^{4}a_{{4}}}{2048}}+{\frac {3\,{a_{{1}}}^{19}{a_{{2}}}^{2}{a_{{4} }}^{2}}{4096}}\\+{\frac {43\,{a_{{1}}}^{17}{a_{{2}}}^{5}a_{{4}}}{4096}}+ {\frac {7\,{a_{{1}}}^{17}{a_{{2}}}^{3}{a_{{4}}}^{2}}{2048}}+{\frac {{a _{{1}}}^{17}a_{{2}}{a_{{4}}}^{3}}{1024}} +\cdots$$

This yields the following sequence for $$Z(Q_n)(B+W)_{B=1, W=1} = Z(Q_n; 2,2,2,\ldots)$$ (colorings with at most two colors): $$2, 6, 42, 1806, 3263442,\ldots$$ which points us to OEIS A007018 as was discovered by the author of the accepted answer.

For the special case of three levels we get the subsituted cycle index $$1/8\, \left( B+W \right) ^{7}+1/4\, \left( B+W \right) ^{5} \left( {B} ^{2}+{W}^{2} \right) +1/8\, \left( B+W \right) ^{3} \left( {B}^{2}+{W} ^{2} \right) ^{2}\\+1/4\, \left( B+W \right) \left( {B}^{2}+{W}^{2} \right) ^{3}+1/4\, \left( B+W \right) \left( {B}^{2}+{W}^{2} \right) \left( {B}^{4}+{W}^{4} \right)$$

which expands to the detailed classification according to the number of black and white nodes $${B}^{7}+3\,{B}^{6}W+7\,{B}^{5}{W}^{2}+10\,{B}^{4}{W}^{3}+10\,{B}^{3}{W }^{4}+7\,{B}^{2}{W}^{5}+3\,B{W}^{6}+{W}^{7}.$$

E.g. the coefficient on $B^6 W$ is three because there are three orbits of nodes.

For the coefficient on $B^5 W^2$ we get the seven possibilities:

1. root node, node on level two
2. root node, node on level three
3. two nodes on level two
4. one node on level two, one node adjacent to it on level three
5. one node on level two, one node not adjacent to it on level three
6. two siblings on level three
7. two non-siblings on level three.

This is the Maple code for this computation, algorithmically extremely straighforward: enumerate all possible combinations of keeping two subtrees of a node in order or flipping them, compute the automorphism that results and factor it into cycles for the contribution to the cycle index.

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;


pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;


bf_build_tree :=
proc(levels, curlev, label, flips)
    local left, right;

    if curlev = levels then
        return [label];
    fi;

    left := bf_build_tree(levels, curlev+1,
                          2*label, flips);
    right := bf_build_tree(levels, curlev+1,
                           2*label+1, flips);

    if flips[label] = 1 then
        return [label, right, left];
    else
        return [label, left, right];
    fi;
end;

bf_collect_autom :=
proc(tree, label, res)
    res[tree[1]] := label;

    if nops(tree) = 3 then
        bf_collect_autom(tree[2], 2*label, res);
        bf_collect_autom(tree[3], 2*label+1, res);
    fi;
end;



pet_cycleind_bf_tree :=
proc(levels)
    option remember;
    local res, ind, flips, allflips, autom, q, src, aut;

    res := 0; allflips := 2^(levels-1)-1;

    for ind from 2^allflips to 2^(allflips+1)-1 do
        flips := convert(ind, base, 2);

        autom := table();
        bf_collect_autom(bf_build_tree(levels, 1, 1, flips),
                         1, autom);

        src := [seq(q, q=1..2^levels-1)];
        aut := [seq(autom[q], q=1..2^levels-1)];

        res := res + pet_autom2cycles(src, aut);
    od;

    res/2^allflips;
end;


bf_2colorings :=
proc(levels)
    option remember;
    local ind;

    ind := pet_cycleind_bf_tree(levels);
    ind := pet_varinto_cind(B+W, ind);

    subs({B=1, W=1}, ind);
end;

bf_2coloringsX :=
proc(levels)
    option remember;
    local ind, q;

    ind := pet_cycleind_bf_tree(levels);
    subs({seq(a[2^q]=2, q=0..levels-1)}, ind);
end;