Catalan numbers, mirror image and walks enumeration

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 n opening and n closing brackets(n-th Catalan number) is equal to:
C_n = \frac{1}{n+1} {2n\choose n}.

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:
path1

Walk encodes proper bracketing, if:

  1. We end on Y=0.
  2. We never go into Y < 0.

(They are named Dyck walks.)

There are {2n\choose n} walks of length 2n that satisfies condition (1). Even more, there are 2n \choose n+k paths that end on Y = 2k.
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.path2

Every walk that satisfies (1) and violates (2) can be 1-to-1 transformed into walk of the same length, that ends on Y=-2. We simply take the first place it reaches Y=-1, and we reflect all further steps. Exactly the same transformation, reflecting all moves after first time we reach Y=-1, takes us back, from all walks ending at Y=-2 to walks ending at Y=0 that violate (2).

So, we have:
C_n = {2n \choose n} - {2n \choose n-1} = {2n \choose n} - \frac{n}{n+1} {2n \choose n} = \frac{1}{n+1} {2n \choose n}

If we are interested in partial fulfilling of (1) and (2), we know that there are 2n \choose n that satisfy (1). How many are there walks that satisfy condition (2)? (how many words of length 2n are prefixes of proper bracketing?)
Such a walks are named Ballot walks, and we will name the number of them as B_n.
We can derive simple recurrence formula:
path3
B_{n+1} = 4\cdot(B_n - C_n) + 2\cdot C_n
(we can extend every Ballot walk in 4 ways, except Dyck walks)

We can use this to prove that B_n = {2n \choose n}:
B_{n+1} = 4\cdot (B_n - C_n) + 2\cdot C_n = 4 {2n \choose n} - 2 \frac{1}{n+1} {2n \choose n} = \\ = \frac{4n+2}{n+1} {2n \choose n} = \frac{(2n+1)(2n+2)}{(n+1)(n+1)} {2n \choose n} = {2n+2 \choose n+1}

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.

path4

path5

Let us try and classificate walks by how much they violate being proper Dyck walk.

  1. For blue walks, we look at how much they violate (1)
  2. For red walks, we look at how much they violate (2)

For example in the picture, we have:

  • 1 blue walk ending at Y=4
  • 3 blue walks ending at Y=2
  • 2 blue walks ending at Y=0
  • 1 red walk reaching lowest point at Y=-2
  • 3 red walks reaching lowest point at Y=-1
  • 2 red walks reaching lowest point at Y=0

So there is hope for a elegant bijection, and we should aim at:
blue walk ending at Y=2k -> (reverse k UPs into DOWNs) -> red walk reaching Y=-k
red walk reaching Y=-k -> (reverse k DOWNs into UPs) -> blue walk ending at Y=2k

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:

path6

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.)

Advertisements

2 responses to “Catalan numbers, mirror image and walks enumeration

  1. Shouldn’t “reflecting all moves after first time we reach Y=1” read “reflecting all moves after first time we reach Y= -1” ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s