Closed form for Lobb Numbers

Question

The Lobb number L(m, n) counts the number of ways that n + m open parentheses and n − m close parentheses can be arranged to form the start of a valid sequence of balanced parentheses.

$L(m, n) = {2n \choose n-m} - {2n \choose n-m-1}$ -- Equation (1)

I have arrived at the following combinatorial argument. First count all combinations $(X_1$) and from this remove the unbalanced parentheses $(X_2)$.

Clearly $X_1 = {2n \choose n-m}$

Now let us focus on $X_2$. Let ')' be the start of an unbalanced sequence.

Case 1: ')' is the first character. In this case, the rest can be filled in ${2n-1 \choose n-m-1}$ ways

Case 2: ')' is the third character. There is a '()' in front. Then the rest can be filled in ${2n-3 \choose n-m-2}$ ways

Case k: )' is the $2k+1'$th character. This implies the first $2k$ characters are balanced and this can be done in $C_k$ ways where $C_k$ is the $k'th$ Catalan number. Then the rest can be filled in ${2n-2k-1 \choose n-m-k-1}$ ways leading to total of $C_k {2n-2k-1 \choose n-m-k-1}$

So $X_2 = \sum_{k = 0}^{k=n-m-1} C_k {2n-2k-1 \choose n-m-k-1}$

Question: How does one go about proving $X_2 = {2n \choose n-m-1}$? Or is there a better combinatorial argument to arrive at Equation (1)?

Answer 1

This is the number of Dyck paths with $n+m$ up-steps and $n-m$ down-steps that never drop below the $x$-axis. These paths necessarily end at $\langle 2n,2m\rangle$. We can use the usual reflection argument to count them. There are altogether $\binom{2n}{n+m}$ paths from $\langle 0,0\rangle$ to $\langle 2n,2m\rangle$. Suppose that a path $\pi$ first drops below that $x$-axis at $\langle k,-1\rangle$ and has $\ell$ up-steps to the right of that point; then it has $2n-k-\ell$ down-steps to the right of that point, and

$$2m+1=\ell-(2n-k-\ell)=2\ell+k-2n\;.$$

If we reflect the part of $\pi$ to the right of that that point in the line $y=-1$, the new path has $\ell$ down-steps to the right of that point and $2n-k-\ell$ up-steps, so it terminates at the point

$$\langle2n,-1-\ell+2n-k-\ell\rangle=\langle 2n,2n-2\ell-k-1\rangle=\langle 2n,-2m-2\rangle\;.$$

The reflection is reversible, since the point at which it started is still identifiable after the reflection, so we have a bijection between ‘bad’ paths — i.e., those that drop below the $x$-axis — and paths from $\langle 0,0\rangle$ to $\langle 2n,-2m-2\rangle$. If such a path has $k$ up-steps and $\ell$ down-steps, we must have $\ell+k=2n$ and $\ell-k=2m+2$, so $2\ell=2n+2m+2=2(n+m+1)$, $\ell=n+m+1$, and $k=n-m-1$. Thus, there are

$$\binom{2n}{n+m+1}=\binom{2n}{n-m-1}$$

such paths and hence

$$\binom{2n}{n+m}-\binom{2n}{n+m+1}=\binom{2n}{n-m}-\binom{2n}{n-m-1}$$

‘good’ paths of length $2n$.

Answer 2

The combinatorial explanation is very nice!

I now complete the proof by induction also:

To prove that $L(m, n+1) = {2n+2 \choose n+1-m} - {2n+2 \choose n-m}$

skipping some steps, we need to prove: $\sum_{k = 0}^{k=n-m} C_k {2n+2-2k-1 \choose n+1-m-k-1} = {2n+2 \choose n-m}$

Substituting $n+1 = s$ in LHS, we get,

$LHS = \sum_{k = 0}^{k=s-m-1} C_k {2s-2k-1 \choose s-m-k-1}$ which is equal to ${2s \choose s-m-1}$ by our induction assumption.

Now we replace $s$ with $n+1$, we get LHS = ${2n+2 \choose n-m}$ exactly as desired.