21.1.14. Surjective Mapping Proof

We want to prove that the number of sequences consisting of n 1s and n -1s, where in each sequence the partial sum at any position is greater than equal to 0 is C(2n, n)/(n+1). For that the proof strategy will be the following. 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.

The proof intends to establish a relationship between sets of sequences, specifically those that follow certain restrictions (set B) and those that do not (set A). Set A comprises all possible arrangements of sequences with n instances of 1s and -1s, without considering any restrictions on their arrangement. The next step is to identify set B, which will contain sequences that do not meet the requirement of keeping partial sums non-negative. Ultimately, to find the number of valid sequences (where all partial sums are non-negative), we will take the total number of sequences (from set A) and subtract those that are invalid (from set B).

Imagine a class of students discussing group projects (set A) where anyone can choose any project without guidelines (no restrictions). Now, suppose the teacher sets certain requirements, indicating which groups should not exceed a certain size (set B). To determine how many groups follow the guidelines, the students can first count all project groups and then subtract those that exceed the size limit to find how many are valid.

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.

To calculate the cardinality (size) of set A, we need to recognize that each sequence consists of n instances of 1s and n instances of -1s. The total number of positions in such a sequence is 2n. The number of ways of choosing n positions for 1s (and thus automatically placing -1s in the remaining positions) is given mathematically by the binomial coefficient C(2n, n). This coefficient counts the combinations of selecting n positions from 2n.

Think of arranging 4 colored balls where two are red (1s) and two are blue (-1s). The total number of arrangements can be visualized as 'choosing' positions for the red balls in a sequence of four positions: it’s like ordering the colors where the positions of red balls can fill 2 out of 4 slots in different arrangements.

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.

To find the cardinality of set B (the bad sequences), we consider sequences that do not satisfy the partial sum conditions and have at least one instance where it dips below zero. Through a mathematical process that involves identifying these sequences, we find that there are C(2n, n+1) such sequences. Thus, by subtracting the cardinality of B from A, we will derive the total count of valid sequences, which correspond to the non-negative partial sums.

Imagine you are organizing a musical performance with a set list (set A) that has 4 songs. However, one of your rules states that at least every two songs must be upbeat (set B). The number of set lists that follow this rule is smaller than the total number of arrangements. By identifying which arrangements fail this rule and subtracting them from the total arrangements, you find how many comply.

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 provides a systematic way to pair each bad sequence (those that violate the partial sum restrictions) with a corresponding valid sequence. This is done by reflecting or flipping the sequence at the point where the first negative sum occurs. By reversing the signs of the numbers leading up to this point in the sequence while keeping the rest intact, we can derive a new sequence with more 1s than -1s, essentially establishing a connection between bad and good sequences.

Consider a hiker aiming to reach a summit, representing a valid sequence. If they accidentally stumble downhill (i.e., reach a negative partial sum), the reflection method is like flipping their route at that point — transforming their route to ensure they now aim back upward (exceeding their previous downward path) towards their goal.

We have established an injective mapping namely the reflection method from the set B to the set C. Now what we will prove is that the above process of converting any bad sequence S to a corresponding sequence S’ that mapping is also a surjective mapping.

An injective mapping means that each bad sequence uniquely corresponds to one good sequence, with no duplicates. In addition to this, we need to prove it is surjective, meaning every valid (good) sequence must have a corresponding bad sequence. This can be shown by taking any sequence from set C and demonstrating that it can be transformed backward into a sequence in set B, confirming that our mappings cover all possibilities.

Think of a library where every book (good sequence) has a unique ISBN (bad sequence). The injective nature ensures that no two books share the same ISBN, while surjectivity ensures that every unique book can be traced back by finding its corresponding ISBN, thereby covering all books in the library without missing any.

And it is easy to see that if we take the partial sum till the rth position it will be negative. Because till the rth position in S’ the sum was positive and the sign of every + 1 and -1 has been reversed. Because of that the partial sum till the rth position S will now become negative. So, we have shown that the mapping is a surjective mapping as well.

This conclusion solidifies our mappings between sets: we have clearly shown that taking any sequence from set C can yield a related sequence in set B, thus proving surjectivity. It ties back to our goal of proving the relationship between sequences with constraints and those without, culminating in finding the Catalan number.

Returning to our library, ensuring that each ISBN traced back reflects a book confirms we have every book accounted for. This ensures that even if some books are lost (bad sequences), we can still find and understand the original content, representing the persevering correlation existing between valid and invalid paths.

--