21.1.8. Reflection Method

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.

In this chunk, we introduce the concept of a 'bad sequence'. A sequence made up of an equal number of 1s and -1s might sometimes have an issue where at some point in the sequence, the cumulative total (or partial sum) is negative. For instance, if you have a sequence like [1, 1, -1, -1], it's valid because the totals at each point do not go below zero. But if you have a sequence like [1, -1, -1, 1], it is deemed 'bad' or invalid because when you reach the second -1, the total becomes negative.

Think of this sequence as a set of bank transactions. If each 1 represents a deposit and each -1 represents a withdrawal, a bad sequence would mean you’ve withdrawn more money than you had at some point in time, leading to an overdraft.

We will find the cardinality of the set B using the reflection method. So, for that let us consider an arbitrary bad sequence and we know that this bad sequence has n number of 1s and n number of –1s and at least one partial negative sum, where exactly the partial negative sum is appearing we do not know.

Here, we discuss a technique known as the 'reflection method' which helps us analyze bad sequences. We begin with a bad sequence without knowing where the first negative partial sum appears. The reflection method will allow us to pair each bad sequence with a new valid sequence that helps in counting them carefully, while showcasing the properties of sequences with negative sums.

Imagine you are looking at a roller coaster. As you rise up (1s), everything seems great. But when you start diving down (-1s), there could be moments that feel too steep. The reflection method allows us to visualize the path of the roller coaster, helping us understand the dips (bad sequences) and ensuring that every dip has a corresponding peak, emphasizing the relationship between these sequences.

Now what we are going to do is corresponding to the bad sequence S; so this is our bad sequence S. We will find another sequence S' which will have n + 1 number of 1s and n number of –1s.

In this chunk, we explain how to create a new sequence (S') from an existing bad sequence (S). The idea is to transform a bad sequence with an equal number of 1s and -1s into a new sequence that has more 1s than -1s. This helps in shifting from a 'bad' situation into a 'better' one where the sequence becomes progressively valid.

Think of this as turning a losing game into a winning one. If you've lost your first game by losing a point (a -1), by flipping the score (reversing a -1 to +1), you can visualize your way back to a positive score, turning negatives into positives.

My claim is this process of getting the sequence S' from the sequence S is an injective process.

We clarify that the transformation from S to S' is injective: Each bad sequence corresponds to a unique new sequence, S'. In other words, if two sequences are different, their reflections will also be different. This uniqueness is crucial to ensure that the one-to-one mapping holds, helping us count valid sequences accurately.

Imagine you are naming your children. Each child has a unique name. While naming, if one name is used, no other can have that name in your household. In this analogy, each bad sequence corresponds to a unique transformation hence ensuring no duplicates arise in our counts.

Now what we will prove is that the above process of converting any bad sequence S to a corresponding sequence S’ is also a surjective mapping.

We establish that the reverse mapping from sequences S' back to the original bad sequences S is surjective. This means that for every sequence in set C (with more 1s), there exists a corresponding bad sequence in set B. This proves both mappings from S to S' and from S' back to S cover all possible sequences adequately, ensuring we have accounted for all valid and invalid arrangements.

Consider a two-way street: Just as every car that goes from point A to point B can also return back, every valid arrangement (S') can trace back to some invalid arrangement (S). This relationship ensures that we fully understand all paths between the two sets.

So, if we find the difference of the cardinality of the A set and B set we get the result of the nth Catalan number which is C(2n, n)/(n + 1).

The last chunk discusses the culmination of our findings: the difference in the number of valid sequences (set A) and the invalid sequences (set B) gives us the Catalan number. The Catalan number is often used in combinatorial mathematics to count various structures like balanced parentheses or paths in a grid, exemplifying its remarkable utility across mathematical disciplines.

Think of this like organizing a tournament. If the total number of matches (total possible arrangements) is a vast number, the valid brackets you can form are fewer, like specific paths to winning. The Catalan number provides a neat way to count those paths among all possible arrangements.

--