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 number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...

s, which count the complete strings of balanced parentheses of a given length. Thus, the ''n''th Catalan number equals the Lobb number ''L''_0,''n''. They are named after Andrew Lobb, who used them to give a simple

inductive proof Mathematical induction is a method for proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots all hold. This is done by first proving a simple case, then ...

of the formula for the ''n''^th Catalan number. The Lobb numbers are parameterized by two non-negative

integers An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

''m'' and ''n'' with ''n'' ≥ ''m'' ≥ 0. The (''m'', ''n'')^th Lobb number ''L''_''m'',''n'' is given in terms of

binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...

s by the formula :

L_ = \frac\binom \qquad\textn \ge m \ge 0.

An alternative expression for Lobb number ''L''_''m'',''n'' is: :

L_ = \binom - \binom .

The triangle of these numbers starts as :

\begin
1 \\
1 & 1 \\
2 & 3 & 1 \\
5 & 9 & 5 & 1\\
14 & 28 & 20 & 7 & 1\\
42 & 90 & 75 &35 & 9 & 1\\
\end

where the diagonal is :

L_=1,

and the left column are the Catalan Numbers :

L_= \frac\binom.

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 sum In mathematics, a series is, roughly speaking, an addition of infinitely many terms, one after the other. The study of series is a major part of calculus and its generalization, mathematical analysis. Series are used in most areas of mathemati ...

s 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 In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives ''p'' votes and candidate B receives ''q'' votes with ''p'' > ''q'', what is the probability that A will be strictly ahead of B throug ...

, first published by

William Allen Whitworth William Allen Whitworth (1 February 1840 – 12 March 1905) was an English mathematician and a priest in the Church of England.. Education and mathematical career Whitworth was born in Runcorn; his father, William Whitworth, was a school headmaste ...

in 1878. The theorem states the

probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...

that winning candidate is ahead in the count, given known final tallies for each candidate.

References

{{DEFAULTSORT:Lobb Numbers Integer sequences Factorial and binomial topics Enumerative combinatorics