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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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 . They are named after Andrew Lobb, who used them to give a simple inductive proof of the formula for the n th Catalan number. 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 : L_{m,n} = \frac{2m+1}{m+n+1}\binom{2n}{m+n} \qquad\text{ for }n \ge m \ge 0. An alternative expression for Lobb number L m,n is: : L_{m,n} = \binom{2n}{m+n} - \binom{2n}{m+n+1} .

The triangle of these numbers starts as : \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 : L_{n,n}=1, and the left column are the Catalan Numbers : L_{0,n}= \frac{1}{1+n}\binom{2n}{n}.…

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. 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 . They are named after Andrew Lobb, who used them to give a simple inductive proof of the formula for the n th Catalan number. 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 L_{m,n} = \frac{2m+1}{m+n+1}\binom{2n}{m+n} \qquad\text{ for }n \ge m \ge 0. An alternative expression for Lobb number L m,n is: L_{m,n} = \binom{2n}{m+n} - \binom{2n}{m+n+1} .

The triangle of these numbers starts as \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 L_{n,n}=1, and the left column are the Catalan Numbers 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.

Ballot counting

The combinatorics of parentheses is replaced with counting ballots in an election with two candidates in Bertrand's ballot theorem, first published by William Allen Whitworth in 18781. The theorem states the probability that winning candidate is ahead in the count, given known final tallies for each candidate.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1262742509 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Lobb number” revision 1262742509 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL