21.1.5. Cardinality of Set A

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.

Set A is a collection of sequences that contain equal numbers of 1s and -1s, meaning for every 1, there is a -1. In this context, we don’t impose any restrictions on the sequences. This means some sequences may have partial sums that drop below zero at some points, while others remain non-negative. The important point is that we are counting all possible sequences with equal numbers of 1s and -1s, regardless of whether the individual sums stay above zero or not.

Think of Set A like a group of basketball players, where each player can score +1 point or lose -1 point. We want to observe all possible game outcomes without any rules; some games may finish negatively if too many points are lost early on, while others might remain positive. We're gathering all results without restrictions.

We will find out the set B of all bad sequences which consist of n number of 1s and n number of –1s which violate the restrictions.

Bad sequences are those that do not meet our requirement of having partial sums that are always greater than or equal to zero. For example, if at any position in the sequence the sum of 1s and -1s falls below zero, that sequence is considered bad. Our goal is to quantify these sequences, which essentially violate the rule of non-negative sums.

Imagine a bank account where you deposit +1 for each dollar earned (1s) and withdraw -1 for each dollar spent (-1s). A 'bad sequence' represents situations where spending occurred before enough income was deposited, causing the balance to drop below zero at some point. We want to count all those spending patterns that resulted in overdrafts.

It is easy to see that the cardinality of the A set is C(2n, n).

The cardinality of set A, which refers to how many sequences are contained within it, can be calculated using the binomial coefficient C(2n, n). This coefficient represents the number of ways to choose n positions for the 1s from a total of 2n positions (where the rest naturally go to the -1s). Hence, regardless of the order of occurrences, this formula gives us the total valid sequences.

Consider arranging two types of objects in a line, where you have n red balls and n blue balls. The number of unique ways to arrange these balls can be computed with the same C(2n, n) formula. This logic applies to our sequences, as the arrangement of 1s and -1s parallels organizing distinct items.

We will show that the cardinality of the set B is C(2n, n+1).

To find the number of bad sequences (set B), we use the reflection method. This method helps us count sequences that have at least one occurrence of a partial negative sum. The number of such sequences can be computed as C(2n, n+1), which is the total arrangements of 1s and -1s where the count of 1s exceeds the count of -1s by one at some point in the sequence.

Imagine the same bank account scenario as before. If you want to find patterns where you overdrew your account at least once, you're counting how many ways there could have been one more withdrawal compared to your deposits. Thus, C(2n, n+1) represents these specific spending patterns, where the spending outstripped income.

The number of valid sequences we want is the difference in cardinality between A and B, expressed as C(2n, n) - C(2n, n+1).

The final step involves calculating the number of valid sequences, which is achieved by subtracting the count of bad sequences from the total count of sequences. Thus, the valid sequences are represented by the formula C(2n, n) - C(2n, n + 1). By performing this subtraction, we isolate sequences that maintain the non-negative partial sum condition we are interested in.

Think of it as calculating the net profits of a business by subtracting negative outcomes (losses) represented by bad sequences from overall outcomes (all transactions). The valid transactions yield the effective business performance, ensuring we only consider profitable scenarios, which aligns with our valid sequences criteria.

--