Advanced combinatorics question: rows with open en closed brackets

Here is a combinatorial proof based upon lattice paths.

We consider paths on a $\mathbb{Z}\times\mathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.

• We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.

• A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.

All paths:

The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $\color{blue}{\binom{2n}{n}}$.

Invalid paths:

A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.

Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $\color{blue}{\binom{2n}{n-1}}$ reflected paths.

Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths: \begin{align*} \binom{2n}{n}-\binom{2n}{n-1}=\color{blue}{\frac{1}{n+1}\binom{2n}{n}} \end{align*}