1
$\begingroup$

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!

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Chopin
    May 10, 2021 at 7:58
  • $\begingroup$ @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. $\endgroup$ May 13, 2021 at 3:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.