How is the diagonal constraint in lattice path needed for the Catalan proofs

binomial-coefficientscatalan-numberscombinationscombinatoricsrecreational-mathematics

I have been reading about the Catalan numbers and how they are they appear in many problems such as:

  • lattice paths
  • valid pair of parenthesis
  • mountains with up/downstrokes
  • non-crossing handshakes
  • rooted plane bushes

The explanations I have seen on why all these problems have the same solution take a rather visual approach. For example:
Mountains vs parenthesis

/\ ()

 /\
/  \  (())  

/\/\/\ ()()()

those seem to make sense trying to show the balance between $2$ symmetric symbols.
When trying to show how we derive the Catalan number all examples I have seen base it on the first example i.e. lattice paths which is basically reduced to the problem of the number of paths going from $(0,0)$ to $(n,n)$ moving only in upwards or to the right i.e. again $2$ symbols ($U$ and $R$) with the additional constraint that the path never goes bellow the diagonal.
I do understand that there is the similarity of having $2$ symbols again, also that we need to have a sequence of the same number of $U$ and $R$ as in the parenthesis and the mountains but I don't really understand how the diagonal constraint fits into all of this.
So taking a specific example i.e. moving from $(0,0)$ to $(3,3)$ we have a valid case bellow staying above the diagonal:
enter image description here

This is equivalent to $U \space R \space U \space R \space U \space R$
Another valid path is $U \space U \space R \space R \space U\space R$
enter image description here

The following violates the diagonal constraint

enter image description here

It is the path: $U \space R\space R\space R\space U \space U$
Again we have the same number of $U$ and $R$ but the condition path is violated.

My question is: How is the condition of the diagonal related with the problem of the valid pair of parenthesis? What changes exactly when we cross the diagonal that reduces the problem to be the same one as the rest?

Best Answer

U corresponds to ( and R corresponds to ). If you cross the diagonal, then at the first point after you cross the diagonal, you have more R's than U's, so you have more ) than ( so the sequence can no longer be completed to a sequence of balanced parentheses. For example, URR becomes ()) which is unbalanced.

Related Question