# Let $P_n$ be the set of all balanced strings of $n$ bracket pairs

I Have the following question:

Let $$P_n$$ be the set of all balanced strings of $$n$$ bracket pairs.

Show that there is a bijection function when given a binary tree, returns a bracket balanced string, such that for each $$n$$: $$f:T_{n+1}\rightarrow P_n$$

My attempt:

$$Solution.$$ We define the function $$f$$ to have a high priority to go down left, and then right. After each left step we want add "(", and after the right step, we shall add ")". This algorithm also called: "pre-order".

Now we have left to show that she is a bijection. We want to see that the amount of possible different trees under $$T_{n+1}$$, equals the amount of all balanced strings of $$n$$ bracket pairs under $$P_{n}$$. Since we know that each tree in $$T_{n+1}$$ is different, then he has unique paths. Thus, for each tree, the algorithm gives a different result in $$P_n$$, so the function is a bijection.

Is what I have shown good enough for what we asked for in this question? I had a different approach to this question when I tried showing an inverse function to $$f$$, given that $$T_n \approx \coprod\limits_{k = 1}^{n - 1} T_k \times T_{n - k}$$, and this formula is almost the same as Catalan one's. I will be glad for some help in this question, see if I am on the right direction or not. Thanks!

Your description is rather vague. I think a more precise way to define it would be as follows:

Let $$e$$ be the non-branching binary tree, and let $$br(a, b)$$ be the binary tree which has left child $$a$$ and right child $$b$$. Note that $$e \in T_1$$, and if $$a \in T_n$$, $$b \in T_m$$, then $$br(a, b) \in T_{n + m}$$.

Define $$f : T \to P$$ as follows:

$$f(e) = \epsilon$$

$$f(br(a, b)) = (f(a)) f(b)$$

To be more precise, $$f(br(a, b)) = (" + f(a) + )" + f(b)$$ where $$+$$ is string concatenation).

Claim: for every tree $$t$$ with $$n + 1$$ leaves, $$f(t)$$ has $$n$$ pairs of brackets.

Proof: this follows immediately from structural induction on $$t$$.

Now, let's discuss why $$f$$ is a bijection. Note the following theorem:

Theorem: for all $$p \in P$$, exactly one of the following is true: $$p$$ is the empty string; or there is a unique pair $$(a, b) \in P^2$$ such that $$p = (" + a + )" + b$$.

I'll omit the proof of this theorem, but it is critical.

Now, we must show that for all $$p \in P$$, there is a unique $$t \in T$$ such that $$f(t) = p$$. This follows from strong induction on the length of $$p$$ and the above theorem.

Thus, $$f$$ is a bijection.

• but isn't it what I have shown? like I said that every different tree has unique paths, and the algorithm will act differently which gives us unique strings. U say that the algorithm isn't right? May 10, 2021 at 7:58
• @aasc232 Your algorithm is the same as mine, you're just describing it really vaguely. You didn't actually prove that $f(x) \in P_n$ whenever $x \in T_{n + 1}$. You also didn't really prove $f$ is a bijection - you just stated it in a vague way (what does it mean to "have unique paths"?). You definitely seem to understand $f$ and intuitively get why it's a bijection, but you didn't actually prove it. May 13, 2021 at 3:19