21.1.9. Claims About 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. That means if I parse the string from a to a, at least at some position k, the values are such that if I just take the sum of a to a then the partial sum is negative.

A bad sequence specifically refers to a sequence made up of equal numbers of 1s and -1s that fails to maintain the rule that the cumulative total (or partial sum) remains non-negative at all points. For example, if at any point in this sequence we find that our cumulative sum becomes negative, that indicates the presence of a bad sequence. In simpler terms, imagine you're walking along a line: if you ever step below the starting point, you've found a negative sum, and thus, your path (or sequence) is considered 'bad'.

Think of a bank account where you start with a balance of $0. If you deposit$1 each time but also occasionally withdraw money (represented by -1), a bad sequence would be any set of transactions that leads your balance below zero at any point. For instance, if you made two deposits of $1 each but then withdrew$3, your account would drop to -$1, demonstrating a bad sequence.

We will introduce a very nice method called as reflection method or why it is called reflection method will be clear very soon. So, we will find the cardinality of the set B using the reflection method.

The reflection method is a technique used to analyze bad sequences by establishing a connection to valid sequences. This approach allows us to count the number of ways we can arrange our sequences while preserving the integrity of the conditions we are studying. Essentially, through this method, we reflect our sequences around critical points where negative sums occur to create valid counterparts. This forms a significant strategy in combinatorial proofs.

Consider a game where you're trying to throw a ball into a hoop. If you miss the hoop to the right, you can 'reflect' that miss to the left side as if you're trying to throw it at an equal distance on the other side of the hoop. By doing so, you can visualize and account for mistakes made in one area of your space, thus covering a broader analysis of your throwing attempts.

Our first claim is that in this bad sequence S the value at the position r is definitely -1. And this is because as per our assumption the partial sum namely the summation of the first r - 1 values is greater than equal to 0.

When analyzing a bad sequence, we make a key observation: at the point where the first negative sum occurs (position r), we can ascertain that the sequence must contain a -1. This stems from the fact that if all of the prior values were non-negative, the introduction of any additional positive value (1) could never have caused the sum to drop below zero without this necessary -1 present in the sequence.

Imagine a scale balancing weights. The left side may have weights that keep the scale balanced or tilted upwards (positive sums), but if you were to drop an additional weight (a +1) without removing any on the left side, it would tip the scale downwards only if you had added a weight that was very heavy on the left side, indicating some negative force (a -1). This illustrates how the presence of a -1 ensures the sum trends negatively.

The process of getting the sequence S’ from the sequence S is an injective process. That means the S’ that are obtained from S are obtained in an injective fashion.

An injective process ensures that each bad sequence corresponds uniquely to a valid sequence between sets, meaning no two bad sequences will yield the same reflected sequence. This property aids in simplifying counts as it guarantees that any analysis performed on these sequences can treat them distinctly and avoid overlap or undercounting.

Think of a vending machine that only gives out drinks in specific cans. If every time you hit a button it dispenses one specific drink that is unique per button press, you can be sure that no two button presses will lead to the same outcome. This mirrors how our sequences work: each unique input (bad sequence) gives rise to one and only one unique output (valid sequence).

We have the set A which is the set of all sequences of equal number of 1s and -1s, without any restriction. We know there are C(2n, n) such strings and we just established that the number of bad sequences which violates the restriction will be C(2n, n + 1).

In essence, by counting the total number of sequences (set A) and subtracting the count of bad sequences (set B) that do not satisfy our restrictions, we arrive at the count of valid sequences. This mathematical framework allows us to calculate the Catalan numbers, which embody the valid configurations available to us given the constraints imposed by the problem.

Imagine calculating how many ways you can arrange books on a shelf. You might start with all possible arrangements but then subtract those which break your rules (like certain books needing to be side by side). This calculation ultimately provides a comprehensive understanding of how many valid configurations exist.

--