21.1.7. Definition of Bad Sequence

So, we will first find out the cardinality or the number of sequences consisting of n 1s and n –1s without any restriction. So, that means let A denote the set of sequences of n 1s and n –1s with no restriction. Then the set A has all the sequences where the partial sums are greater than equal to 0, as well as it has all the sequences where the partial sum at every k may not be greater than equal to 0.

This chunk introduces Set A, which involves all possible combinations of n 1s and n -1s without any restrictions on their arrangement. To understand this, consider a scenario where you have pairs of socks: red (1s) and blue (-1s). In this set, you're allowed to mix and match without worrying about how many reds you have versus blues at any given time. The cardinality, or the total number of these combinations, is given by the binomial coefficient C(2n, n) because you're simply choosing locations for n 1s in a total of 2n positions (the other n will automatically be for -1s).

Imagine you're filling a bag with 5 red balls (1s) and 5 blue balls (-1s). If you don't care about whether more red or blue are on top at any point, the total ways you can arrange these 10 balls is your Set A. It's like making a mixed fruit salad where all fruits are allowed together without any restriction.

Now what we will show is that the cardinality of the set B is C(2n, n+1) and if we subtract the cardinality of B from the cardinality of A then we will get our required answer. A sequence is a bad sequence if it consists of n number of 1s, n number of –1s such that in such a sequence there is at least one occurrence of a partial negative sum.

This chunk defines what constitutes a 'bad sequence'. A bad sequence is one that, despite having the correct amount of 1s and -1s, has an arrangement that dips below certain thresholds (specifically, where a running total is negative at any point). To see why this matters, think of balancing a checking account. If you deposit $1 (1s) and withdraw$1 (-1s), but at some point, you owe more than you have, you're in 'bad' territory despite having an equal number of transactions. The notation C(2n, n+1) indicates that there are situations where, after arranging your 1s and -1s, you can end with one more 1 than -1 in the worst configurations.

Consider a seesaw. If one side has 5 people (1s) and the other side has 5 coins (-1s), the balance is fine. However, if at some point during play, the seesaw tips too far down on one side, even briefly, that arrangement is like a bad sequence—it's a moment when the total weight is skewed negatively.

We will introduce a very nice method called as reflection method. So, 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.

In this portion, we introduce a technique called the reflection method to analyze bad sequences. The method works by essentially 'flipping' the representation of 1s and -1s at the first point of negativity in a bad sequence. Imagine looking into a mirror: your left hand becomes the right and vice versa. Similarly, this method helps illuminate how many structures can be fixed or reconfigured to avoid a negative outcome.

Picture a swing in a playground. As the child swings back and forth (1s and -1s), if they swing too far back and risk going over (a negative), you can think of the reflection method as a way to turn them around and correct course before they fall. The reflection allows you to consider new arrangements that maintain balance.

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. So, that means that if we are at rth position S is negative and it must be a -1.

In this chunk, we ascertain initial properties of bad sequences. The claim that the first negative sum occurs at a position where there's a -1 is fundamental to understanding why bad sequences are, in fact, 'bad'. If prior values balanced positively, the next must have tipped negatively, indicating that it was a -1. Therefore, this insight is critical in classifying sequences and understanding their structure.

Imagine you are trying to balance books on a shelf. If you've added enough books (1s) to one side that the weight shifts to the negative so it tips (becomes -1), you can clearly identify the book that caused it to tip over based on your current balance.

So now let us count the number of 1s and –1s in the sequence S’. So, after flipping signs, we need to consider how many each will contribute. This is a crucial part of the reflection method.

When discussing the mappings created by the reflection method, we talk about how flipping the bad sequences into new valid arrangements generates distinctive outcomes. Each bad sequence relates directly and uniquely to a new sequence of 1s and -1s—this straightforward relationship is known as injectivity, ensuring that no two distinct bad sequences produce the same good sequence. This principle reinforces the connection between the sequences and mathematically validates our reflections.

Think of a unique fingerprint. Each individual (bad sequence) has a distinct print (good sequence), and even if two people might share the same characteristics, their prints will not match. Thus, every method of reconfiguring maintains its uniqueness, akin to how our reflection process works.

--