A BIJECTIVE PROOF OF AN IDENTITY CONCERNING NODES OF FIXED DEGREE IN PLANTED PLANE TREES

JOHN W. MOON AND HELMUT PRODINGER

1. Introduction

We consider planted plane trees, which are rooted, embedded into the plane and enumerated by Catalan numbers y_{n} = \frac{1}{n} \binom{2n−2}{n−1}; see e.g. [2].

In [1], among other things, the following was considered. Denote by y_{nd} the number of (planted plane) trees of size n and root degree d. (It is easy to see that y_{nd} = \frac{d}{n−1} \binom{2n−3−d}{n−2}, a ballot number.) Also, denote by D_{nd} the total number of nodes of degree d in trees of size n. It was shown by generating function arguments that D_{nd} = 2\binom{2n−3−d}{n−2}, whence

d D_{nd} = 2(n − 1) y_{nd} .  (1)

It is this formula (1) that we will “explain” combinatorially in the present note. Example.

[figure] Figure 1. n = 4, y^{4} = 5, y^{41} = 2, y^{42} = 2, y^{43} = 1, D^{41} = 12, D^{42} = 6, D^{43} = 2.

Remark. In the case of labelled trees, the equivalent of formula (1) reads simply D_{nd} = n y_{nd}.

2. The bijection

Consider the D_{nd} trees of size n with root node r and a designated node u of degree d. Let L denote the set of d D_{nd} (partially coloured) trees obtained by assigning (a) the

colour red to the node r and to the left–most edge incident with r and (b) the colour blue to the designated node u and to one of the d edges incident with u. (Note that it is possible for a node or an edge to receive both colours.)

Now consider the y_{nd} trees of size n in which the root node has degree d.

Let R denote the set of 2(n − 1)y_{nd} (partially coloured) trees obtained by assigning (a) the colour blue to the root node and to the left–most edge incident with the root node and (b) the colour red to one of the n − 1 edges of the tree and to one of the two nodes incident with this red edge.

Date: September 11, 1997.

To see that the sets L and R are equivalent, it suffices to regard each tree in L as being rooted at its blue node with the blue edge as the left–most edge incident with the root. (Or, conversely, we may regard each tree in R as being rooted at its red node with the red edge as the left–most edge incident with the root.)

Remark. Let c_{0}(= 1), c_{1}, c_{2}, … denote a sequence of constants and suppose each rooted plane tree T is assigned the weight

w(T) = ∏_{v∈V (T)} c_{d(v)}

where V (T) denotes the set of nodes of T and d(v) denotes the number of edges incident with node v that lead away from the root of the tree. Let N_{β}(T) denote the number of nodes of degree β in a tree T and let

N_{n}(α, β) = ∑ N_{β}(T) w(T)

where the sum is over all (weighted rooted plane) trees T of size n and root degree α. Then the relation

β c_{β} c_{α−1} N_{n}(α, β) = α c_{α} c_{β−1} N_{n}(β, α)  (2)

follows by a slight extension of the bijective argument used above.

References

[1] A. Meir and J. W. Moon. Survival under random coverings of trees. Graphs and Combinatorics, 4:49–65, 1988.

[2] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

Department of Mathematical Sciences, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1

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

  E-mail address: jwmoon@vega.math.ualberta.ca, Helmut.Prodinger@tuwien.ac.at
  WWW-address: http://vega.math.ualberta.ca/People/Facultypages/Moon.J.html,
http://info.tuwien.ac.at/theoinf/proding.htm