A BIJECTION BETWEEN COLOURED TREES AND SET PARTITIONS

HELMUT PRODINGER

Marcu considered in a recent paper [2] colourings C(T, n, k) of a (labelled) tree T with n nodes and k colours, such that adjacent nodes have different colours and all the colours are really used. Furthermore, colourings, which are only different with respect to a permutation of the colours, are identified. The number of such colourings is

\left\{{n − 1 \atop k − 1}\right\} ,

with Stirling numbers of the second kind [1].

Now, these numbers \left\{{n \atop k}\right\} are most prominent as the number of partitions of the set {1, 2, …, n} into k classes (blocks).

Therefore, in this note, we will construct a bijection between the colourings C(T, n, k) and the partitions of the set {1, 2, …, n − 1} into k − 1 classes.

Assume that a set partition is given. We further assume that the nodes of the tree are labelled by 1, 2, …, n in an arbitrary but fixed way. We will call node n the root. We identify “classes” with “colours” and use the “old” colours {1, 2, …, k − 1} and a “new” colour k.

• We start by temporarily colouring each node except the root by the class in which it is.

• The root gets the new colour (the k–th colour).

• Then we work through the tree, node by node, starting at the neighbours of the root, going to the leaves. If the current colour of a node does not lead to a contradiction (same colour as the neighbour in the direction of the root), we stick to the old colour. Otherwise, we change it to the new colour.

Now, by construction, it is a correct colouring, and k colours are used. And the process is reversible: The class of node n has to be removed, and all the nodes with this colour go into the same class as its neighbour (in the direction of the root.)

This process has some similarity with an old bijection appearing in [3].

We illustrate the bijection by the following example.

Here, n = 23, and we start with the set partition a := {7, 16, 17, 18, 19, 20, 22}, b := {2, 5, 6, 8, 9, 11, 13, 14}, c := {1, 3, 4, 10, 12, 15, 21}. The root is node 23, and it gets colour d. Node 20 can stay with colour a, but then node 7 cannot have colour a, so it get colour d. Node 18 can stay with a, and 8 with b, but then 5 must get d. Etc; the whole colouring is this:

Date: November 7, 1996.

\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ c & b & d & c & d & b & d & b & b & c & b & c & d & b & c & d & d & a & a & a & d & d & d \end{matrix}

[figure: 9; 10; 5; 8; 16; 3; 4; 22; 11; 19; 17; 12; 21; 2; 13; 14; 1; 6; 15; 23; 20; 7; 18]

Figure 1. An example of the bijection

References

[1] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[2] D. Marcu. A note on trees colouring. Demonstratio Mathematica, 29:577 –578, 1996.

[3] H. Prodinger. On the number of Fibonacci partitions of a set. The Fibonacci Quarterly, 19:463–466, 1981.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

  E-mail address: Helmut.Prodinger@tuwien.ac.at
  WWW-address: http://info.tuwien.ac.at/theoinf/proding.htm