Kreweras, G. and P. Moszkowski, Tree codes that preserve increases and degree sequences, Discrete Mathematics 87 (1991) 291-296.
We define a bijection from the set .Y,, of rooted Cayley's trees with n vertices to the set [l, n]"-' of words of n -1 letters written with the alphabet [l, n]. This code has three remarkable properties:
(1) As in Priifer's code [l], the degree of every vertex is visible in the word mr = m,(l). . . m&n -1) coding the tree T. More precisely, if di denotes the degree of the vertex i:
If i is the root of T, then i appears d, times in rnT If not, then i appears d, -1 times in mT.
(2) For any rooted tree, increasing (or decreasing) edges can be defined in the following way: let (i, j) be an edge of T such that the minimal path joining i to the root passes through j; then the edge (i, j) is said to be increasing if j > i (and decreasing if j < i) [2]. In other words, if c is the contraction representing T, the edge (i, c(i)) is increasing if c(i) > i. We prove that the set of letters i in mT such that m,(i) > i corresponds to the set of increasing edges of 7'.
c(i)>i
Cs mr(i)>i.
(3) From the code mT one derives a code m(T) for Cayley's trees which 'preserves' degrees and increases of edges. The code m(T) can be defined independently of mT and therefore from it one derives a bijective proof of Cayley's formula [6].
These properties yield new generating functions.
The bijections generalize the classic bijection between permutations linking cycles to outstanding elements [4] (while the bijections of Egecioglu and Remmel [2], which have similar properties, may be viewed as variants of Joyal's code [5]).