Free Hint for HW3 Problem 3

We need a bijection on dyck paths that “switches” the a and b statistics.  Fortunately there are a lot of things in bijection with dyck paths, so we can transform the problem. I just wanted to share one way of doing this.

Consider the bijection with binary trees as performing Depth-First Search and

-if you move through an edge going to the left for the first time go up
-if you move through an edge going to the right for the first time go down

What are the statistics a and b under this bijection? And what kind of bijection between binary trees can ‘switch’ them? Note that the bijection we are looking for needs to send UU…UD…D (dyck path of first going all steps Up and the all Down) to UDUD…UD. If you draw the corresponding trees, you’ll see the perfect candidate for bijection.

Of course, this is only one of the many (more than 100!) equivalent formulations of the problem.

 

Advertisements

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

%d bloggers like this: