21.1. Catalan Numbers - Derivation of Closed Form Formula

In the last lecture, we discussed various problems whose solutions constitute Catalan numbers. In this lecture, we will continue our discussion on Catalan numbers and we will derive a closed form formula for the recurrence relation for Catalan numbers.

The introduction sets the stage for the lecture by recapping previous discussions on Catalan numbers and indicating the goal of the current lecture: to derive a closed-form formula. Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursive structures.

Consider a parenthesis balancing problem, which can be likened to organizing a stack of dishes. Every time you put a dish on top, it represents an opening parenthesis, and taking one off represents a closing one. The valid sequences of stacking dishes depict the structure of Catalan numbers.

We recall from the last lecture that we discussed two problems whose solutions are the Catalan numbers. The first problem was about counting valid strings of n pairs of parentheses. Second, we looked at sequences of n ones and n negative ones that have a partial sum greater than or equal to zero.

Two classic problems are identified: the valid parenthesis problem and the sequence problem involving ones and negative ones. These problems highlight how Catalan numbers can be derived from combinatorial interpretations involving matched pairs and constraints on sums.

Think of matching socks: for every left sock (opening parenthesis), there must be a right sock (closing parenthesis) for a match. Similarly, in the sequences with +1s and -1s, you want to ensure that at any point in time, you do not have more right socks than left socks in your drawer.

We saw a bijection between the set of sequences consisting of n 1s and n -1s where each partial sum is greater than equal to 0 and the set of all valid strings with n pairs of opening and closing parentheses.

A bijection indicates a one-to-one correspondence between two sets. By establishing a relationship between valid sequences of parentheses and certain sequences of +1s and -1s, we can derive properties of Catalan numbers from understanding these two forms.

Imagine you are organizing a race with runners (+1s) and hurdles (-1s). The runners can only progress if they successfully overcome the hurdles at the same rate they come. This mirrors how valid sequences must balance the +1s and -1s, akin to matching parentheses.

Let A denote the set of sequences of n 1s and n -1s with no restriction. Then, set A includes strings with valid and invalid sequences. Set B consists of 'bad sequences' which violate the restrictions.

Set A represents all potential sequences of +1s and -1s, while Set B captures the sequences that fail to meet the criteria of non-negativity in their partial sums. The strategy to derive the Catalan number will be to evaluate these sets and find the difference in their cardinalities.

Consider a school where students (1s) can participate in events and students who need help (–1s). Set A includes all students wanting to join any club (valid or invalid) while Set B includes only those students who disrupt the formation of clubs by needing help at incorrect times.

To find the cardinality of set B, we introduce the reflection method which will help in counting the bad sequences.

The reflection method serves as a powerful technique to analyze and count ‘bad sequences’ by relating them to ‘good sequences’ through a reflection process, ensuring a clear mapping from disallowed to allowed scenarios.

Imagine you are building a wall (sequence of +1s) but occasionally, the bricks are placed incorrectly (–1s, representing bad sequences). By reflecting on the mistakes, you can learn how to rearrange the wall properly, ensuring all bricks fit as needed (valid sequences).

The reflection method is introduced to find the cardinality of bad sequences by transforming such sequences into ones with an excess of +1.

This transformation leverages the idea of action and reaction: when a sequence goes negative, we can mirror that portion to create a valid sequence that has more +1s. This mechanism provides a systematic way to count sequences that would otherwise be complicated to analyze.

Think of a person climbing a mountain where they occasionally slip back (representing negative values). Instead of counting every slip individually, we can visualize them climbing back up (reflecting), making it easier to see how many steps they took correctly.

We establish that the transformation from bad sequences to sequences with two more 1s (n+1) is both injective and surjective.

By proving that the reflection method consistently generates unique and comprehensive mappings, we can conclude that the cardinality of bad sequences corresponds to those valid sequences with the necessary excess.

In a classroom setting, if you send students for extra credit (mapping sequences) based on who needs help and who is excelling, ensuring that each student is either accounted for or has a counterpart in the other mix demonstrates a perfect correspondence.

The cardinalities are computed: A has C(2n, n) and B has C(2n, n+1). The difference gives the nth Catalan number.

The relationship between the sizes of Set A and Set B yields the desired Catalan number through a simple arithmetic operation. This final computation underlines the elegance of combinatorial reasoning in generating these important values.

Imagine organizing a library (Set A) where half the books are fiction and half are non-fiction. If you know some books were misplaced (bad sequences), estimating how many books were correctly placed against the total helps determine the efficiency of your cataloging.

--