21.1.11. General Process of S' Construction

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.

A bad sequence is defined as a sequence containing equal numbers of 1s and -1s that at some point yields a negative partial sum when summed from the start. This means that if you tally up the values step by step, you will eventually come across a point at which your running total dips below zero. The focus here is to understand how to quantify these bad sequences, as they are crucial to the overall counting of valid sequences.

Imagine counting steps while hiking. If each step forward is a +1 (1), and a slip backward is a -1 (-1), a bad sequence is when your total steps lead you down a slope (negative sum), which is like slipping into a negative score during a hike.

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

The reflection method is a technique used to map bad sequences to their corresponding valid sequences by reflecting them across a certain threshold. This reflection changes the sign of the elements in the bad sequence from that point onward, creating an equivalent sequence that has more 1s than -1s. Essentially, this technique allows us to convert bad sequences into valid structures, making it easier to count them.

Think of the reflection method as shining a flashlight. If you shine the light on a dark corner and it reveals the shapes of objects there, you can see what was hidden in the shadows. Similarly, when we reflect bad sequences, we reveal valid structures that were hidden within the negative sums.

Now, for each of these bad sequences S, I have highlighted the first occurrence of partial negative sum in that sequence. Corresponding to the sequence S there will be another sequence S’ which will have n + 1 number of 1s and n –1 number of –1s.

In this step, each bad sequence is transformed into a new sequence by taking the found first negative point and making corresponding changes to create a sequence that has an excess of 1s. Specifically, if originally S has equal parts of 1s and -1s, we create a new sequence S' that has two more 1s than -1s by 'flipping' the symbols after the first negative occurrence. This ensures S' will have a positive sum overall, illustrating the transformation from the invalid to the valid.

Imagine you are baking cookies and accidentally put in too many chocolate chips (1s); the reflection method is akin to realizing you need more basic dough (1s) to counterbalance your sweetness so that your cookies turn out perfect.

My claim is this process of getting the sequence S’ from the sequence S is an injective process. 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.

Injective mapping means that every bad sequence can be converted into a unique valid sequence through the reflection method—no two bad sequences will yield the same valid sequence. Surjective means that for every valid sequence, there is at least one bad sequence that can be transformed into it using the reverse of the reflection. Together, these properties ensure a one-to-one correspondence between bad sequences and a larger framework of valid sequences, allowing us to count them effectively.

Think of it like creating a unique playlist from a list of songs (bad sequences) where every playlist is distinctly curated without repetition (injective). If every mood has a song (surjective), it ensures there's a song for every feeling you have, forming a perfect connection from your emotions to your playlist.

And if we find the difference of the cardinality of the A set and B set we get the result of the nth Catalan number.

The cardinality of the set A represents all possible sequences of n 1s and n -1s, which is given as C(2n, n). From this, we subtract the count of bad sequences from set B (C(2n, n + 1)) to find the number of sequences that are valid—these are the structures counted by the Catalan numbers. This subtraction helps us isolate only those sequences that maintain the desired properties and do not violate initial conditions.

Imagine balancing a budget where A represents all your potential expenses and B indicates those that would lead to overspending. Calculating your expenses while excluding those that break the bank will give you your actual budget (the nth Catalan number), helping you stay financially healthy.

--