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.

### Like this:

Like Loading...

*Related*

## Recent Comments