(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)
Looking at Wikipedia page for Binary Trees, I've noticed this assertion that the number of rooted binary trees of size $n$ would be this Catalan Number: $$C_n = \dfrac{1}{n+1}{2n \choose n}$$
But I don't understand how I could come up with such a result by myself? Is there a method to find this result?
Now, what if the order of sub-trees (which is left, which is right) is not considered? For example, from my point of view, I consider that these two trees are the same:
/\ /\ /\ /\ Would it be possible to apply a similar method to count how many of these objects have exactly $n$ nodes?
Asked By : Stéphane Gimenez
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/368
Answered By : uli
For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.
An excellent reference is Analytic Combinatorics by the late Philipe Flajolet and Robert Sedgewick. It is available from the link above.
The late Herbert Wilf's book generatingfunctionology is another free source.
And of course Concrete Mathematics by GKP is a treasure trove.
For binary trees it goes like this: First you need a clear definition of the tree.
A binary tree is a rooted tree in which every non-leaf node has degree 2 exactly.
Next we have to agree what we want to call the size of a tree.
On the left all nodes are equal. In the middle we distinguish the leaves and non-leaves. On the right we have a pruned binary tree where the leaves have been removed. Notice that it has unary branches of two types (left and right)!
Now we have to derive a description of how these combinatorial objects are built. In the case of binary trees a recursive decomposition is possible.
Let $\mathcal{A}$ be the set of all binary trees of the first type then symbolically we have:
It reads as: "An object of the class of binary trees is either a node or a node followed by two binary trees." This can be written as equation of sets:
$$\mathcal{A}=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{A}\times\mathcal{A}\bigr)$$
By introducing the generating function $A(z)$ that enumerates this class of combinatorial objects we can translate the set equation into an equation involving the generating function.
$$A(z)=z+zA^2(z)$$
Our choice of treating all nodes equally and taking the number of nodes in the tree as notion of its size is expressed by "marking" the nodes with the variable $z$.
We can now solve the quadratic equation $zA^2(z)-A(z)+z=0$ for $A(z)$ and get, as usual, two solutions, the explicit closed form of the generating function:
$$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$$
Now we simply need Newton's (generalized) Binomial Theorem:
$$(1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k$$
with $a=1/2$ and $x=-4z^2$ to expand the closed form of the generating function back into a power series. We do this because, the coefficient at $z^n$ is just the number of combinatorial objects of size $n$, typically written as $[z^n]A(z)$. But here our notion of "the size" of the tree forces us to look for the coefficient at $z^{2n+1}$. After a little bit of juggling with binomials and factorials we get:
$$[z^{2n+1}]A(z)=\frac{1}{n+1}\binom{2n}{n}.$$
If we start with the second notion of the size the recursive decomposition is:
We get a different class of combinatorial objects $\mathcal{B}$. It reads: "An object of the class of binary trees is either a leaf or a interal node followed by two binary trees."
We can use the same approach and turn $\mathcal{B}=\{\square\}\cup\bigl(\{\bullet\}\times\mathcal{B}\times\mathcal{B}\bigr)$ into $\mathcal{B}=1+zB^2(z)$. Only this time the variable $z$ only marks the internal nodes, not the leaves, because the definition "the size" is different here. We get a different generating function as well:
$$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$
Extracting the coefficient yields
$$[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}.$$
Class $\mathcal{A}$ and $\mathcal{B}$ agree on the counts, because a binary tree with $n$ internal nodes has $n+1$ leaves, thus $2n+1$ nodes in total.
In the last case we have to work a little harder:
which is a description of non-empty pruned binary tries. We extend this to $$\begin{align}\mathcal{C}&=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\\\mathcal{D}&=\{\epsilon\}\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\end{align}$$
and rewrite it with generating functions
$$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$$
solve the quadratic equations
$$\begin{align}C(z)&=\frac{1-2z-\sqrt{1-4z}}{2z}\\D(z)&=\frac{1-\sqrt{1-4z}}{2z}\end{align}$$
and get yet again
$$[z^n]C(z)=\frac{1}{n+1}\binom{2n}{n}\quad n\ge1 \qquad [z^n]D(z)=\frac{1}{n+1}\binom{2n}{n} \quad n\ge0$$
Note that the Catalan generating function is
$$E(z)=\frac{1-\sqrt{1-4z}}{2}$$
it enumerates the class of general trees. That is the trees with no restriction on the node degree.
$$\mathcal{E}=\{\bullet\}\times\mathrm{SEQ}(\mathcal{E})$$
It reads as: "An object of the class of general trees is a node followed by a possible empty sequence of general trees."
$$E(z)=\frac{z}{1-E(z)}$$
With the Lagrange-Bürmann Inversion Formula we get
$$[z^n]E(z)=\frac{1}{n+1}\binom{2n}{n}$$
So we proved that there are as many general trees as there are binary trees. No wonder there is a bijection between the general and binary trees. The bijection is known as the rotation correspondence (explained at the end of the linked article), that allows us two store every general tree as a binary tree.
Note that if we do not distinguish the left and right sibling in class $\mathcal{C}$ we get yet another class of trees $\mathcal{T}$:
the unary binary trees. $$\mathcal{T}=\{\bullet\}\times\mathrm{SEQ}_{\le2}(\mathcal{T})$$ They have a generating function too $$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$$ however their coefficient is different. You get the Motzkin numbers $$[z^n]T(z)=\frac{1}{n}\sum_k\binom{n}{k}\binom{n-k}{k-1}.$$
Oh and if you don't like generating functions there are plenty of other proofs too. See here, there is one where you could use the encoding of binary trees as Dyck words and and derive a recurrence from their recursive definition. Then solving that recurrence gives the answer too. However the symbolic method saves you from coming up with the recurrence in the first place, as it works directly with the blueprints of the combinatorial objects.
Post a Comment