I always enjoyed seeing short and elegant proofs of theorems that I knew before.
I really enjoy this short proof that number of proper placing of opening and closing brackets(-th Catalan number) is equal to:
for example, there are 2 ways to properly place 2 opening and 2 closing brackets, out of 6 total ways:
())(, )((), )()(, ))((
First, we may transform the problem into one about walks on plane.
If we take (0,0) as a starting position, and assign to ‘(‘ a walk into UP-RIGHT direction, and ‘)’ a walk into DOWN-RIGHT direction, we might encode sequences of brackets. So, encoding of ((())))(() is:
Walk encodes proper bracketing, if:
- We end on .
- We never go into .
(They are named Dyck walks.)
There are walks of length that satisfies condition (1). Even more, there are paths that end on .
Now, the fun part. Instead of trying to enumerate walks that satisfy condition (2), we will enumerate those that break it. In fact, we will use reflection method.
Every walk that satisfies (1) and violates (2) can be 1-to-1 transformed into walk of the same length, that ends on . We simply take the first place it reaches , and we reflect all further steps. Exactly the same transformation, reflecting all moves after first time we reach , takes us back, from all walks ending at to walks ending at that violate (2).
So, we have:
If we are interested in partial fulfilling of (1) and (2), we know that there are that satisfy (1). How many are there walks that satisfy condition (2)? (how many words of length are prefixes of proper bracketing?)
Such a walks are named Ballot walks, and we will name the number of them as .
We can derive simple recurrence formula:
(we can extend every Ballot walk in 4 ways, except Dyck walks)
We can use this to prove that :
Is this a coincidence? If the number of walks that keep property (1) is equal to the number that keeps property (2), maybe we can find some elegant bijection between one set to another. (Of course there exists any bijection..)
Think about it for a second, it is a nice excercise.
Let us try and classificate walks by how much they violate being proper Dyck walk.
- For blue walks, we look at how much they violate (1)
- For red walks, we look at how much they violate (2)
For example in the picture, we have:
- 1 blue walk ending at
- 3 blue walks ending at
- 2 blue walks ending at
- 1 red walk reaching lowest point at
- 3 red walks reaching lowest point at
- 2 red walks reaching lowest point at
So there is hope for a elegant bijection, and we should aim at:
blue walk ending at -> (reverse k UPs into DOWNs) -> red walk reaching
red walk reaching -> (reverse k DOWNs into UPs) -> blue walk ending at
Can we identify k such an edges in a red walk? Let us take edge that takes us first time from 0 to -1, first edge from -1 to -2, …, first edge from -(k-1) to -k, and reverse them:
And as we see, it is actually a bijection, because we can nicely reverse this operation:
We reverse last edge taking edge from 0 to 1, last edge from 1 to 2, …, last edge from (k-1) to k.
Nice, clean, and certainly more clean than inductive proof :)
(I would like to thank Yao-ban Chan for ideas for this post.)