0
$\begingroup$

A well-formed parenthesization $\beta$ of size $n$ is an expression with $n$ $($ symbols, $n$ $)$ symbols such that for any substring of $\beta$, the number of right parentheses is less than or equal to half the length of the substring and the first symbol is a left parenthesis. For instance, here are the well-formed parenthesizations of length $3: (())(), ()(()), ((())), ()()(), (()())$ Find a bijection between the set of well-formed parenthesizations of size $n$ and the set of Dyck paths from $(0,0)$ to $(2n,0)$. Find a bijection between the set of well-formed parenthesizations of size $n$ and the set of binary trees with $n$ nodes (binary trees are trees or acyclic graphs with at most $2$ children per node).

This'll basically show that the cardinalities of all three sets is ${2n\choose n}\dfrac{1}{n+1},$ the nth Catalan number, since I know that the number of well-formed parenthesizations of size $n$ is the nth Catalan number. I think a bijection between the set of well-formed parenthesizations of size $n$ and Dyck paths from $(0,0)$ to $(2n,0)$ where the valid directions are either NE or SW, can be specified by simply replacing each $($ symbol with NE and each $)$ with SW. That's because by the definition of a well-formed parenthesization, there are never more right parentheses than left parentheses in any given prefix, so the corresponding path from $(0,0)$ to $(2n,0)$ will never go below the $x$-axis. Also, if one has a Dyck path that never goes below the $x$-axis, the corresponding parenthesization will be well-formed because for any prefix, there will be at most as many left and right parentheses and the total number of left and right parentheses will be equal.

But I'm not really sure how to find a bijection between binary trees and well-formed parenthesizations. I know how to show that the number of binary trees with $n$ nodes, say $b_n$, obeys the recursive formula for the Catalan numbers: $b_n = b_0b_{n-1} + b_1b_{n-2} + \cdots + b_{n-1}b_0,$ but I'm not sure how this'll help.

$\endgroup$
0
$\begingroup$

In this answer I showed a bijection between well-formed parenthesizations of length $n$ and full binary trees with $n+1$ leaves. (A full binary tree is one in which each node has $0$ or $2$ children.) There is a bijection between full binary trees with $n+1$ leaves and binary trees with $n$ nodes.

To see this, let $T$ be a full binary tree with $n+1$ leaves, and let $m$ be the number of non-leaf nodes of $T$. Then $T$ has $n+m+1$ nodes, so it must have $n+m$ edges. On the other hand, the sum of the degrees of its nodes is $n+3m$: each leaf has degree $1$, the root has degree $2$ (if $n>0$), and the other non-leaf nodes have degree $3$. Thus, $n+3m=2(n+m)$, and $m=n$. Thus, what’s left when we remove all of its leaves from $T$ is a binary tree with $n$ nodes.

Conversely, suppose that $T$ is a binary tree with $n$ nodes. Let $\ell$ be the number of leaves of $T$ and $s$ the number of nodes with exactly one child. Give each leaf of $T$ two children, and give each non-leaf with only one child its missing child, and let $T'$ be the resulting tree. Clearly $T'$ is a full binary tree with $2\ell+s$ leaves, since its leaves are precisely the added nodes. Now the sum of the degrees of the nodes of $T$ is

$$\ell+2s+3(n-\ell-s)-1\,.$$

(The last term is because the root has no parent.) This is twice the number of edges of $T$, and $T$ has $n-1$ edges, so

$$\ell+2s+3(n-\ell-s)-1=2n-2\,,$$

and $2\ell+s=n+1$. Thus, $T'$ is a full binary tree with $n+1$ leaves. Clearly removing the leaves from $T'$ yields $T$, so we have our bijection.

Combine these two bijections, and you have what you want.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy