Lobb number

In combinatorial mathematics, the Lobb number L_m,n counts the 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.^[1]

Lobb numbers form a natural generalization of the Catalan numbers, which count the complete strings of balanced parentheses of a given length. Thus, the nth Catalan number equals the Lobb number L_0,n.^[2] They are named after Andrew Lobb, who used them to give a simple inductive proof of the formula for the n^th Catalan number.^[3]

The Lobb numbers are parameterized by two non-negative integers m and n with n ≥ m ≥ 0. The (m, n)^th Lobb number L_m,n is given in terms of binomial coefficients by the formula

${\displaystyle L_{m,n}={\frac {2m+1}{m+n+1}}{\binom {2n}{m+n}}\qquad {\text{ for }}n\geq m\geq 0.}$

An alternative expression for Lobb number L_m,n is:

${\displaystyle L_{m,n}={\binom {2n}{m+n}}-{\binom {2n}{m+n+1}}.}$

The triangle of these numbers starts as (sequence A039599 in the OEIS)

${\displaystyle {\begin{array}{rrrrrr}1\\1&1\\2&3&1\\5&9&5&1\\14&28&20&7&1\\42&90&75&35&9&1\\\end{array}}}$

where the diagonal is

${\displaystyle L_{n,n}=1,}$

and the left column are the Catalan Numbers

${\displaystyle L_{0,n}={\frac {1}{1+n}}{\binom {2n}{n}}.}$

As well as counting sequences of parentheses, the Lobb numbers also count the ways in which n + m copies of the value +1 and n − m copies of the value −1 may be arranged into a sequence such that all of the partial sums of the sequence are non-negative.