20.4.2. Bijection Between Problems

So, we want to find out how many valid strings of n pairs of parentheses we can have. And what is my definition of valid strings of n pairs of parentheses. Well if I parse that string from left hand side to right hand side. Then it should be the case that each left parenthesis or opening parenthesis should have a corresponding matching closed parenthesis. That is what is my definition of a valid string of n pairs of parentheses.

So, for instance this string is valid, because if you scan from left hand side to right hand side then each instance of opening parenthesis has a corresponding matching closing parenthesis. It is not the case that you have an occurrence of closing parenthesis but till that point you do not have an occurrence of a corresponding opening parenthesis. In the same way this is a valid sequence ( ) ( ), but this is invalid ( ))(.

In this chunk, we define what valid strings of parentheses are. A valid string requires that for every opening parenthesis, there is a corresponding closing parenthesis. The examples provided illustrate what makes a string valid or invalid. If you can traverse through the string from the beginning to the end and each opening parenthesis finds its matching closing parenthesis, the string is valid. If at any point you encounter a closing parenthesis without a corresponding opening parenthesis prior, then the string is invalid.

Imagine you are putting on gloves: for every left glove you wear, you need a right glove to complete the pair. If you start with a right glove and don't have a corresponding left glove available, that pairing is like an invalid parenthesis string. Just like you can’t wear mismatched gloves at once, a valid string of parentheses requires that every opening parenthesis has an appropriate closing one.

If we show that there is a bijection between the set of each valid parenthesis, each valid way or each valid mechanism of parenthesizing n + 1 numbers and a set of valid strings that you can formulate with n pairs of parentheses. Then we can say that the solution for both the problems is the Catalan number.

This chunk discusses how to establish a bijection between two sets: the valid parenthesizing of n + 1 numbers and the valid strings of parentheses. A bijection is a one-to-one correspondence that ensures that each element in one set maps uniquely to an element in another set. If such a mapping can be demonstrated, it can be concluded that both problems share the same solutions - which in this case, corresponds to Catalan numbers.

Think of a dance event where each participant is paired for a dance. If we say that every pair of dancers corresponds to a unique way of ordering partners, we can establish a bijection by matching every dance formation to a unique partner arrangement. Just as each unique dance formation has distinct dancers assigned to each role, every valid parenthetical expression corresponds to a unique way of structuring operations.

But it turns out that even though you get a valid string consisting of n pairs of parentheses. This is not an injective mapping. Because as per this process the sequence where b and c are multiplied first and then the product is multiplied by a will lead to this sequence. Because you will forget about a you will forget about dot return the left parenthesis and then you again have a left parenthesis.

In this section, it is pointed out that the original method for constructing a valid string from a parameterized sequence does not yield a one-to-one mapping, which is critical for establishing a bijection. This occurs because different sequences can yield the same valid string, undermining the injectiveness required for a mathematical bijection.

Consider a situation where different roles in a play can be filled by the same actor. If you had multiple scenes where one actor performs multiple roles, you may see the same character appear under different scenarios, creating ambiguity. This overlap leads to confusion in casting - similar to how two different multiplication orders can produce identical strings of parentheses.

So, how exactly we go from this set to this set. We have to convert a valid ordering of specifying the multiplication order into a string of n pairs of parentheses in a slightly different way and this is done as follows. So, you take any multiplication order specified by your parenthesizing and you erase all the terms x to xn and you erase all the left parenthesis as well. But you retain the dots and the right parenthesis.

This section describes a refined method to correctly establish a bijection between the sequences and valid parentheses strings. It details the process of stripping away certain elements from the multiplication order, specifically the variables and the left parentheses, while retaining critical elements such as dots and right parentheses. This alteration aims to correct the injectiveness issue from the previous steps.

Imagine tidying up a messy room for a party. You might decide to remove all distractions (toys, clutter) that don’t belong, while keeping essential items like chairs for sitting and decorations that provide ambiance. In this analogy, the remaining items represent the elements kept during the mapping process to derive the valid parentheses strings.

But we cannot have a sequence of the form where I say start with 1 and then I have a -1 and then I have a -1, that is not allowed. Because if I take this partial sum s in this sequence then s becomes -1, so that is not allowed.

Closing this section, the impossibility of starting a valid sequence with a negative increment is emphasized. This reinforces the conditions necessary for sequences derived from the parenthetical structures to remain valid, which ties back into the idea of Catalan numbers representing several combinatorial structures.

It's like running a race where the rule is you must always remain ahead, never falling behind the starting line. Starting with a negative value is akin to making a false start and being disqualified, underscoring the stringent requirements needed for creating valid sequences and structures in our mathematical context.

--