21.1.6. Cardinality of Set B

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. And then we will find out the set B of all bad sequences and by bad sequences I mean the sequences consisting of n number of 1s and n number of –1s which violate the restrictions. And of course then it is easy to see that the required value or value of the required number of sequences of n 1s and n –1s where the partial sums are greater than equal to 0 will be the difference of the cardinality of the A set and the B set.

In this chunk, we introduce two sets of sequences: Set A and Set B. Set A includes all possible sequences made up of n 1s and n -1s without restrictions on their sums. In contrast, Set B is a collection of sequences that violate specific conditions, meaning they contain a partial sum that is negative at least once. The goal is to find the cardinality (or size) of both sets. To determine the number of valid sequences (those where partial sums are always non-negative), we will eventually compute the difference between the sizes of these two sets: |A| - |B|.

Think of Set A as a box containing all possible outfits made up of n shirts and n pairs of pants. Set B is a smaller box inside it with outfits that do not match in style—these are the 'bad' ones that violate fashion rules. To find out how many stylish outfits we have (those that follow the rules), we just count all outfits in the larger box and subtract the amount of mismatched outfits in the smaller box.

So, it is easy to see that the cardinality of the A set is C(2n, n). This is because, what is the set A? It is the set of all sequences with n number of 1s and n number of –1s where we do not put any restriction whatsoever over the partial sums in the sequences. So, any sequence in this set will have n number of 1s and n number of –1s. So, it is easy to see that the cardinality of A is nothing but the number of ways in which we can find out n locations out of 2n locations where we can put the 1s. Because once we find out the n locations where we can put the 1 the remaining locations are of course has to be occupied by –1.

In this chunk, we calculate the size (cardinality) of Set A, denoted as C(2n, n). This represents the number of ways to arrange n 1s and n -1s in sequences. Since we have 2n total spots and must choose n of them to place 1s, the remaining spots will naturally be filled with -1s. Hence, the formula C(2n, n) represents this counting method and captures all unrestricted combinations of sequences of 1s and -1s.

Imagine you have 2n boxes and you want to put n apples (1s) in them. The rest of the boxes (also n) will have oranges (-1s). The total ways to choose which boxes out of the 2n should contain apples is what we need to find—it is simply like selecting the spots to place your apples, ensuring every box is filled.

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 chunk emphasizes on defining what a 'bad sequence' is. A bad sequence includes n occurrences of both 1s and -1s, but fails to uphold the required condition of having non-negative partial sums. In other words, as we go through the sequence, we encounter at least one instance where the sum of the values falls below zero, marking it as invalid. This understanding is crucial for determining the size of Set B.

Consider a project where you are trying to keep a budget balanced (the sums), using income (1s) and expenses (-1s). A bad sequence would be a scenario where at any point, your expenses outweigh your income, leading to a negative balance. Thus, you cannot accept this budget plan—much like how we cannot accept bad sequences in our context.

So, now we will show 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.

In this portion, we reveal that the cardinality of the bad sequences (Set B) is C(2n, n + 1). This represents the number of ways to arrange sequences where, for some partial sums, a negative value appears. The realization of this size computation is essential as it allows us to establish the required relationship to find the valid sequences by subtracting the size of Set B from Set A.

Returning to our budget analogy, if we consider all possible combinations of income and expenses (Set A), and we know the number of bad budget combinations (Set B) that lead to negative balances, we can easily compute how many budgets maintain non-negative balances simply by subtracting those bad combinations from the total.

So, what we will do is 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.

In this segment, we introduce the concept of the reflection method as a technique to calculate the cardinality of Set B. The reflection method involves analyzing bad sequences by reflecting them in such a way that allows for a straightforward computation of the valid sequences they can correspond to. Understanding this method is pivotal for grasping how to derive the results for Set B.

Imagine you're building a bridge that has to stay above the river (valid sequences). Each time you encounter a sagging part (bad sequences), you reflect it upwards to see how high the bridge needs to be above the river. By doing this, we get a clearer idea of how many bridges are structurally sound and follow the necessary rules.

--