\documentstyle[a4,12pt,emlines2]{amsart}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\hfuzz=10pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\theorembodyfont{\slshape}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\def\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}
\def\Pr{\operatorname{Pr}}
\def\poch#1#2{#1^{\underline{#2}}}
\def\stir#1#2{\left\{#1\atop#2\right\}}
\RequirePackage{theorem}



\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

\newcommand{\ackno}{\subsection*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}


\begin{document}
\title
[coloured trees and set partitions]
{A bijection between coloured trees and set partitions}
\author[H.~Prodinger]
{Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{Helmut.Prodinger@@tuwien.ac.at\vskip0pt
{\it WWW-address{\rm :\ }}\texttt{http://info.tuwien.ac.at/theoinf/proding.htm}
}


\date{\today}

\maketitle


Marcu considered in a recent paper \cite{Marcu96} 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
\begin{equation*}   
\stir{n-1}{k-1}\;,
\end{equation*}
with Stirling numbers of the second kind \cite{GrKnPa94}.

Now, these numbers $\stir nk$ are most prominent as
the number of partitions of the set $\{1,2,\dots,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,\dots,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,\dots,n$ in an arbitrary but fixed way. We will call
node $n$ the {\sl root.\/}
We identify  ``classes'' with ``colours'' and use the ``old'' colours $\left\{1,2,\dots,k-1\right\}$ and a ``new'' colour $k$. 


\begin{itemize}
\item We start by temporarily
colouring each node except the root by the class in which it is.
\item The root gets the new colour (the $k$--th colour).
\item 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.    
\end{itemize}

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 \cite{Prodinger81}.

\bigskip

We illustrate the bijection by the following example.

Here, $n=23$, and we start with the set partition $a:=\left\{7,16,17,18,19,20,22\right\}$,
$b:=\left\{2,5,6,8,9,11,13,14\right\}$, $c:=\left\{1,3,4,10,12,15,21\right\}$.
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:

\Large{
\begin{equation*}   
\begin{smallmatrix}   \setcounter{MaxMatrixCols}{23}
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{smallmatrix}
\end{equation*}
\par}

\normalsize{
\begin{figure}[h]  
%\input{marcu.pic} 
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(125.00,108.33)
\put(29.00,44.67){\circle*{2.11}}
\put(36.67,54.67){\circle*{2.11}}
\put(44.33,64.67){\circle*{2.11}}
\put(52.00,74.67){\circle*{2.11}}
\put(59.67,84.67){\circle*{2.11}}
\put(67.33,94.67){\circle*{2.11}}
\put(75.00,104.67){\circle*{2.11}}
\put(62.00,55.33){\circle*{2.11}}
\put(79.67,46.00){\circle*{2.11}}
\put(97.33,36.67){\circle*{2.11}}
\put(115.00,27.33){\circle*{2.11}}
\put(79.33,69.00){\circle*{2.11}}
\put(122.00,83.33){\circle*{2.11}}
\put(104.67,69.67){\circle*{2.11}}
\put(52.00,17.67){\circle*{2.11}}
\put(59.67,27.67){\circle*{2.11}}
\put(67.33,37.67){\circle*{2.11}}
\put(71.67,2.00){\circle*{2.11}}
\put(33.00,92.00){\circle*{2.11}}
\put(50.67,82.67){\circle*{2.11}}
\put(50.33,105.67){\circle*{2.11}}
\put(30.67,64.33){\circle*{2.11}}
\put(38.33,74.33){\circle*{2.11}}
\emline{29.00}{44.67}{1}{36.67}{55.00}{2}
\emline{36.67}{55.00}{3}{44.33}{64.67}{4}
\emline{44.33}{64.67}{5}{62.00}{55.33}{6}
\emline{62.00}{55.33}{7}{68.00}{37.67}{8}
\emline{68.00}{37.67}{9}{60.00}{27.67}{10}
\emline{60.00}{27.67}{11}{52.33}{17.67}{12}
\emline{52.33}{17.67}{13}{72.00}{2.00}{14}
\emline{30.33}{64.33}{15}{44.33}{64.33}{16}
\emline{44.33}{64.33}{17}{38.67}{74.00}{18}
\emline{38.67}{74.00}{19}{33.33}{91.67}{20}
\emline{45.00}{65.00}{21}{52.00}{74.67}{22}
\emline{52.00}{74.67}{23}{80.00}{69.00}{24}
\emline{80.00}{69.00}{25}{104.67}{69.67}{26}
\emline{104.67}{69.67}{27}{122.33}{83.00}{28}
\emline{67.33}{37.67}{29}{79.67}{46.00}{30}
\emline{67.33}{37.67}{31}{97.33}{36.67}{32}
\emline{68.00}{37.67}{33}{115.00}{27.33}{34}
\emline{52.00}{74.67}{35}{50.67}{83.00}{36}
\emline{52.00}{74.67}{37}{59.33}{84.67}{38}
\emline{59.33}{84.67}{39}{67.67}{94.67}{40}
\emline{67.67}{94.67}{41}{75.33}{104.67}{42}
\emline{67.33}{94.67}{43}{50.33}{105.67}{44}
\put(79.33,106.33){\makebox(0,0)[cc]{9}}
\put(53.67,108.33){\makebox(0,0)[cc]{10}}
\put(66.67,99.00){\makebox(0,0)[cc]{5}}
\put(64.67,85.33){\makebox(0,0)[cc]{8}}
\put(50.67,86.67){\makebox(0,0)[cc]{16}}
\put(37.67,94.00){\makebox(0,0)[cc]{3}}
\put(41.33,77.00){\makebox(0,0)[cc]{4}}
\put(49.67,65.67){\makebox(0,0)[cc]{22}}
\put(29.00,67.67){\makebox(0,0)[cc]{11}}
\put(41.00,53.67){\makebox(0,0)[cc]{19}}
\put(32.33,42.00){\makebox(0,0)[cc]{17}}
\put(66.67,56.33){\makebox(0,0)[cc]{12}}
\put(62.67,38.00){\makebox(0,0)[cc]{21}}
\put(56.00,29.67){\makebox(0,0)[cc]{2}}
\put(46.33,18.00){\makebox(0,0)[cc]{13}}
\put(75.67,5.33){\makebox(0,0)[cc]{14}}
\put(84.33,47.33){\makebox(0,0)[cc]{1}}
\put(102.67,38.67){\makebox(0,0)[cc]{6}}
\put(118.00,31.00){\makebox(0,0)[cc]{15}}
\put(81.33,73.33){\makebox(0,0)[cc]{23}}
\put(103.33,73.67){\makebox(0,0)[cc]{20}}
\put(125.00,79.67){\makebox(0,0)[cc]{7}}
\put(48.00,75.33){\makebox(0,0)[cc]{18}}
\end{picture}
\caption{An example of the bijection}
\end{figure}
\par}



\bibliographystyle{plain} 



%\bibliography{pro_bib}

\begin{thebibliography}{1}

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.

\bibitem{Marcu96}
D.~Marcu.
\newblock A note on trees colouring.
\newblock {\em Demonstratio Mathematica}, 29:577 --578, 1996.

\bibitem{Prodinger81}
H.~Prodinger.
\newblock On the number of {F}ibonacci partitions of a set.
\newblock {\em The Fibonacci Quarterly}, 19:463--466, 1981.

\end{thebibliography}



\end{document}






