21.1.2. First Problem: Strings of Parentheses

In the last lecture, we discussed various problems whose solutions constitute Catalan numbers. The first problem was that of coming up with the number of strings with n pairs of opening and closing parentheses where a string is called valid, if whenever we scan the string from left to right then at any point of time or at any position in the string the number of each instance of an opening parenthesis has a closing parenthesis.

In this chunk, we introduce the concept of valid parentheses sequences. A valid sequence requires that at any point while scanning from left to right, the total number of opening parentheses encountered should never be less than the closing ones. This ensures that every opening parenthesis has a corresponding closing parenthesis, which is essential for the sequence to be valid.

Think of a valid parentheses sequence like a balanced scale. When you place an item on one side (an opening parenthesis), you need to place an item of equal weight on the other side (a closing parenthesis) to keep it balanced.

The second problem that we saw in the last lecture is that of coming up with a number of sequences consisting of n number of 1s and n number of -1s such that if we scan the string from the first position to the last position then each partial sum should be greater than equal to 0.

This chunk introduces a second problem that mirrors the idea of valid parentheses but uses sequences of 1s and -1s instead. Here, each 1 represents an opening parenthesis and each -1 represents a closing one. The requirement that each partial sum should be greater than or equal to 0 corresponds directly to the condition that the number of closing parentheses must never exceed the opening ones as we parse through the sequence.

Imagine you're keeping track of your savings account balance (the partial sum). Every time you receive money, you add 1; every time you spend, you deduct 1. Your balance should never drop below zero, mirroring the requirement for valid parentheses sequences.

And we saw a bijection between the set of sequences consisting of n 1s and n -1s where each partial sum is greater than equal to 0 and the set of all valid strings with n pairs of opening and closing parenthesis.

In this chunk, we highlight an important relationship or bijection between two sets of sequences: one formed by n 1s and n -1s with non-negative partial sums, and another formed by valid strings of parentheses. Establishing this bijection helps in proving that both sequences count the same combinatorial objects — they are two different ways to represent the same mathematical concept.

Imagine two different representations of the same item. For instance, a physical object can be represented by both a diagram and a description in words. Here, the parentheses sequences and the sequences of 1s and -1s represent the same underlying structure, just in different forms.

So, now for the rest of our discussion our focus will be to find out the cardinality of the set of bad sequences and what is a bad sequence? A sequence is a bad sequence if it consists of n number of 1s, n number of -1s such that in such sequence there is at least one occurrence of a partial negative sum.

This part delves into defining 'bad sequences' — sequences that violate the valid condition by having at least one partial sum that dips below zero. This is critical as it sets the ground for determining how many valid sequences exist by subtracting bad sequences from the total sequences.

Picture this as a game where you collect points (1s) and lose points (-1s). If at any point in the game your score drops below zero, you are considered to have made a 'bad move' which correlates to our 'bad sequence' definition.

So, what we will do is we will introduce a very nice method called as the reflection method. We will find the cardinality of the set B using the reflection method.

The reflection method provides a systematic approach to associating each bad sequence with a new valid sequence. This new sequence reflects the properties of the bad one, allowing us to effectively count the number of bad sequences through this reflective transformation. It leverages symmetry in combinatorial structures to facilitate counting.

Imagine a ball thrown against a wall; when it bounces back (reflects), it represents how we can visualize bad sequences transforming into valid ones. It's a clever way to assess the total number of bad sequences using their transformations.

--