21.1.15. Summary of Cardinality

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.

The cardinality of set A represents the total number of sequences that can be formed using n pairs of 1s and –1s without any restrictions on their order. The notation C(2n, n) indicates the binomial coefficient, which counts the number of ways to choose n positions from a total of 2n positions (the total number of symbols in the sequence) to place the 1s. Once the positions for the 1s are chosen, the remaining positions will automatically be filled with –1s.

Imagine you have 2n boxes where you need to fill n boxes with blue balls (1s) and n boxes with red balls (–1s). The different combinations of filling these boxes represent the possible sequences. C(2n, n) tells you how many unique ways you can choose the positions for the blue balls while the rest will be red.

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.

Set B is composed of sequences where there is at least one instance of a partial negative sum, meaning that at some position in the sequence, the cumulative sum goes negative. The cardinality of set B is represented as C(2n, n + 1), indicating that for any sequence in B, if you attempt to form a corresponding valid sequence by adding one more 1, you will exceed the total capacity for equal distribution, thus leading to a negative sum at some point.

Think about it like a balance scale: if you have equal weights on both sides, it stays balanced. Now, if you add an extra weight on one side, it tips the scale, causing it to become 'negative' (out of balance). The additional 1 is like the extra weight, tipping the balance in favor of negatives.

So, as mentioned, 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.

To find the number of valid sequences from the total sequences (set A) and the invalid sequences (set B), we simply calculate the difference: |A| - |B|. This difference gives us the number of valid sequences where at no point does the cumulative sum of the 1s and –1s drop below zero, aligning with the definition of a valid sequence.

Consider a balance again: you have 100 balanced threads (set A) representing all ways to tie knots; however, if you accidentally loop some threads incorrectly (set B), the remaining ways that remain taut (the valid sequences) are simply those that minus out the erroneous loops. The difference gives you your correctly tied knots.

We will find the cardinality of the set B using the reflection method. This method involves taking a bad sequence and reflecting it to find a corresponding valid one with an adjusted number of 1s and –1s.

The reflection method acts as a tool to visualize and count the invalid sequences by illustrating that each bad sequence can 'reflect' or transform into a valid one by reversing the signs. This reflection shows how each bad sequence contributes to understanding the arrangement of valid sequences based on their properties, allowing for a clear mapping between bad sequences and adjusted valid sequences.

Imagine walking along a path and accidentally stepping into a ditch (the bad sequence); the reflection method helps you visualize how to climb out of the ditch, transforming that moment of struggle back into a normal path. Each step reflects a choice to either avoid the ditch or navigate back to solid ground, demonstrating how struggles can guide better decisions.

--