4
$\begingroup$

Consider a row with open and closed brackets. A row is correct if for each open bracket there is a unique closed bracket further in the row. In other words: if this row of brackets can be seen as a correct mathematical expression from which all numbers and operation symbols are omitted. Or again in other words: for each point in the row, the amount of open brackets for this point has to be at least the amount of closed brackets for this point.

Show that the number of correct rows with $n$ pairs of brackets is given by $\frac1{n+1} \binom{2n}{n}$.

Remark: Following statements can (you don't have to use them) give some inspiration (you'll need more arguments and the given statements are not written in the correct order!):

  • If a row of brackets does not satisfy the conditions (bad row), then there is a point $\dots$ on which the number of closed brackets exceeds the number of the open brackets for the first time.
  • An alternative row is a row with $n-1$ open brackets and $n+1$ closed brackets.
  • It's clear that $g \circ f$ is the identity map on the bad rows and that $f \circ g$ is the identity map on the alternative rows. This implies that $f$ and $g$ are bijections.
  • $$\binom{2n}{n} - \binom{2n}{n-1} = \dots = \frac1{n+1} \binom{2n}{n}$$
  • "... change all open brackets on positions $2k+2, \dots, 2n$ in this alternative row $r$ into closed brackets ..."

I have no idea how to start with this proof. Any clues? Thanks a lot!

$\endgroup$
5
$\begingroup$

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.

enter image description here

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*}

$\endgroup$
1
$\begingroup$

This answer does not really provide a proof.

It might be helpful though, especially by the link and if Catalan numbers are new to you.

Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.

Note that a row is correct if for every pair $(i,j)$ we have $i\geq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.

The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.