(Catalan number) ((Dynamic Programming) (Reflection Principle))

The problem

I was reading the book Algebra(Gelfand & Shen) and encountered this problem:

The program

I am not sure what this problem looks like in the eyes of an algebra chad, but in the eyes of a programmer like me, this smells like a DP problem. I might actually have solved a LeetCode problem that is similar to this before, although I cannot recall which one. By possible ways to put parentheses, it literally means grouping them into pairs, only that once you form a pair, itself will be treated as a single number in the next round. For example, in 1 + (2 + 3), 2, 3 is a pair, and then 1, (2 + 3) is another pair.

Simply put, we need to divide and conquer, split the expression to left and right parts, say the left side have $n$ different ways to allocate parentheses and $m$ ways on right side, in total we should get $m\times n$ different combinations. Do this process recursively since each has its own subexpressions, until you end up with only one or two numbers in the subexpression, which is the base case. Finally, we need to consider all different ways to split the expression.

Notice that regardless of the position, all subexpressions that contain the same amount of numbers also have the same allocations, this is what we can memoize during the process, instead of doing the same calculations repeatitively.

By now we have everything we need to solve this problem, we can literally directly translate this process in code using an recursive function, but there is a simpler way, doing it the other way around, using bottom-up DP.

Given the following observation:

Ways to split $n$ numbers are:

That is, $S_n = \sum_{i=1}^{n-1} S_i \times S_{n-i}$, if you know $S_1,S_2,\ldots,S_{n-1}$, you can get $S_n$. We might as well first solve $S_1$, then $S_2$, and so on. It transforms the code from recursion to a simple traverse.

def counting(n): 
	if n <= 2: return 1
	
	dp_table = [0 for_ in range(n)]
	dp_table[0] = 1  # base case S1
	dp_table[1] = 1  # base case S2

	for i in range(2, n):
		for j in range(1, i+1):
			dp_table[i] += dp_table[j-1] * dp_table[i-j]

	return dp_table[-1]

A new path

Until now this is still a regular, textbook style solution, what is interesting is that, somehow I feel like this problem can be solved using a combinative approach, but I could not figure out how, then I consulted the omniscient Mr. ChatGPT. Turned out it is true, there is a very elegant way to solve it. The rest of this article is me trying to explain what ChatGPT taught me, it is not my original idea, I am learning it through writing it down in my own words.

Strip out all ornaments, the problem has nothing to do with the algebra expression but with counting ways to construct valid parentheses pairs. And what is a valid parentheses pair?

1. Apparently there should be equal amount of left and right parentheses in total.
2. Starting from the beginning, at no position should there be more right parentheses than left ones.
   For example, )(() is not valid since at position 1, there are 1 ) and 0 (, it fails to pass 2 although it satisfies 1.

Transformation

Now we are gonna make a leap here. We can substitute ( with -1 and ) with +1, after all it is all about binary choice at each pos, but we get an extra benefit, we can sum them up now, it should not be hard to see that by doing this, we transform the conditions to:

1. Total sum is zero.
2. Starting from the beginning, the cumulative sum should never exceed 0, $S_j=\sum_{i=1}^j v_i\le 0, j=1,2,3,\ldots,n$.
   we can do some simple tests:

Examples:

This is invalid as the running sum at position 1 is 1 $>$ 0.

This one is valid.

Reflection Principle

Time to introduce our main guest, the reflection principle.

Consider a simpler version of the problem, what are possible ways to arrange +1 and -1 so that they satisfy rule 1? Trivial, half of them are +1. Say we have $n$ values in total, the answer is $\binom{n}{n/2}$ ways (notice that $n$ is always even in our problem).

The difficult part is rule 2, among all paths that satisfy rule 1, how many of them have a running sum that is greater than or equal to 1 at some point (those are invalid paths, as we’ll see later). That is where the reflection principle comes in.

If we invert all values after the first time we encounter 1, it doesn’t matter where, only when (the first time). That is,+1 will be replaced with -1, -1 with +1. Say the first 1 happens at position $m$, then we do $\underbrace{v_1,\ldots,v_m}_{\text{unchanged}}, \underbrace{v_{m+1},\ldots,v_n}_{\text{inverted}}.$ What can we expect?

Well the running sum until $m$ is $\sum_{1}^{m} v_i = 1$, we know the final sum is 0, the sum of the remaining numbers $\sum_{m+1}^{n} v_i$, it should be $0-\sum_{1}^{m} v_i=0-1=-1$. Now because we inverted all values from $m+1$ to $n$, $\sum_{m+1}^{n} w_i=\sum_{m+1}^{n} -v_i=-\sum_{m+1}^{n} v_i=1$. Thus the new total sum, $\sum_{1}^{m}v_i + \sum_{m+1}^{n}w_i=1+1=2$.

You might wonder, what if there is no 1 along the path? It is outside our interest here, it does not count. You might also wonder why the first time, not the second time, well, if we do that, all those who only reach 1 once will not be counted.

An example:

Now the magic, the above process basically tells us that, for all paths whose cumulative sum ends at 0 and reaches 1 or above at some point, i.e., whose greatest running sum is greater than or equal to 1, there is one unique inverted version whose running sum ends at 2; And for each path whose cumulative sum ends at 2, it must have one entry in the original set, as it reaches 2 at the end, it must have reached 1 as well, and if you perform the same inversion on it, you get exactly one path in the original set.

In other words, for each original path, there is only one inverted path, and for each inverted path, there is only one original path. Therefore to count the inverted path is to count the original path..

That is an important revelation, because counting paths whose total sum is 2 is trivial, we have $n$ numbers, $m$ of them are 1, total sum being 2, $m+(n-m) \times (-1)=2, m=\frac{n+2}{2}$. There are $\binom{n}{\frac{n+2}{2}}$ paths have a total sum of 2, which is equal to the number of paths whose running sum ends at 0 and reaches 1 at some point.

Again, $n$ is always even because we are talking about pairs of parentheses if you still remember the original problem, and if you do, we have one final step. I mentioned before that we are counting invalid paths, and there are $\binom{n}{n/2}$ paths that satisfy rule 1, so the number of valid paths is $\binom{n}{n/2}-\binom{n}{\frac{n+2}{2}}$.