20.4.1. Formulation of Valid Strings

So, here we want to find out how many valid strings of n pairs of parenthesis we can have. And what is my definition of valid strings of n pairs of parenthesis? 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 parenthesis.

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.

This chunk introduces the concept of valid strings of parentheses, which is a key focus of combinatorial counting problems. A valid string means that at no point when reading the string from left to right should there be more closing parentheses than opening ones. This ensures that every opening parenthesis has a corresponding closing one. For example, the string '(()())' is valid because every '(' has a matching ')'. However, a string like '())(' is invalid because there is a closing parenthesis that does not have a preceding opening parenthesis to match.

Consider a pair of parentheses as a gate. For every time you open a gate (which represents an opening parenthesis), you need to eventually close it (which represents a closing parenthesis). If you try to close a gate that was never opened, it results in chaos, just like an invalid string of parentheses!

In the same way this is a valid sequence ( ) ( ), but this is invalid ( ) )(.

Because you have an opening bracket and then a closing bracket and then followed by a closing bracket. For that you do not have a corresponding opening bracket as of now. So, that is why this is an invalid string. So, we want to find out how many such valid strings of n pairs of parenthesis we can have.

This chunk further illustrates valid and invalid strings through specific examples. It reinforces that valid strings must maintain the proper order of parentheses, meaning every opening bracket must be matched by a closing bracket before encountering additional closing brackets. For instance, '(())()' is valid because all opening parentheses are matched correctly, while '())(' breaks this rule when it attempts to close a parenthesis without prior opening.

Imagine a system of locks and keys where each lock represents an opening parenthesis and each key represents a closing one. A valid string of parentheses corresponds to a proper setup where every lock has a matching key to open it before you can close any locks. An invalid string occurs when you try to close a lock without first opening it with a corresponding key.

So, I have demonstrated here the total number of ways of formulating valid strings of n pairs of parenthesis for different values of n. If n is equal to 0 then you do not have any string. And so that no string is denoted by an empty string, the star denotes empty string. And since empty string is one of the strings that is why for n equal to 0; I consider that answer is 1.

This chunk discusses how to count valid strings for different values of n, particularly highlighting the base case when n=0. For n=0, the only valid string is the empty string, which demonstrates that there's exactly one valid arrangement when no pairs exist. This concept is a crucial part of determining a general formula for computing the number of valid strings for any n, where n represents the number of pairs of parentheses.

Think of n pairs of parentheses like pairs of shoes. If you have 0 pairs, naturally, there is only one state you can have: no shoes. This represents the scenario of n=0. As we increase the number of pairs, the complexity of arranging them increases, just like organizing multiple pairs of shoes in a wardrobe.

So, now we want to find out or derive a formula for general value of n. It turns out that the general value of n or the number of strings for general n is nothing but the value of the nth Catalan number.

This chunk sets up the goal of finding a general formula for the number of valid strings of parentheses as a function of n, revealing that this number is represented by the Catalan numbers. The recurrence relation established for counting parenthesis arrangements leads to a mathematical formula that can yield the count of valid arrangements for any given n. Catalan numbers arise frequently in combinatorics and specifically relate to the counting of structured objects like valid parentheses strings.

Imagine you are a librarian and need to categorize books on a shelf. The way you arrange books can follow specific rules similar to how parentheses open and close. You might have multiple valid ways to arrange them, just as there are many valid strings of parentheses. The Catalan number would tell you exactly how many valid ways you have to set up your books, given a specific number of them.

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 parenthesis. Then we can say that the solution for both the problems is the Catalan number.

In this chunk, the focus is on establishing a bijection between valid string arrangements and valid parenthesizing of numbers, indicating that each valid arrangement of parentheses corresponds to a unique valid way of calculating the product of numbers. This bijection highlights a fundamental concept in combinatorial mathematics, where proving such relationships allows for insights into the counting of structured objects in different contexts.

Think of each valid string of parentheses as a unique recipe with specific steps. Just like a recipe uses precise actions (like mixing or baking) to achieve a dish, a valid set of parentheses organizes operations for calculating values. Each unique recipe (or string) perfectly aligns with distinct sets of calculations (or products), showing how order and structure matter in both cooking and mathematics.

--