Lobb number

In combinatorial mathematics, the Lobb number Lm,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.[1]

Lobb numbers form a natural generalization of the Catalan numbers, which count the number of complete strings of balanced parentheses of a given length. Thus, the nth Catalan number equals the Lobb number L0,n.[2] They are named after Andrew Lobb, who used them to give a simple inductive proof of the formula for the nth 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 Lm,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.

As well as counting sequences of parentheses, the Lobb numbers also count the number of 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.

References

  1. Koshy, Thomas (March 2009). "Lobb's generalization of Catalan's parenthesization problem". The College Mathematics Journal 40 (2): 99–107. doi:10.4169/193113409X469532.
  2. Koshy, Thomas (2008). Catalan Numbers with Applications. Oxford University Press. ISBN 978-0-19-533454-8.
  3. Lobb, Andrew (March 1999). "Deriving the nth Catalan number". Mathematical Gazette 83 (8): 109–110.
This article is issued from Wikipedia - version of the Wednesday, December 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.