Número de Lobb

En matemáticas combinatorias , el número de Lobb L _{m , n} cuenta las formas en que n  + m paréntesis de apertura y n − m paréntesis de cierre pueden organizarse para formar el inicio de una secuencia válida de paréntesis balanceados . ^{[ 1 ]}   

Los números de Lobb constituyen una generalización natural de los números de Catalan , que cuentan las cadenas completas de paréntesis balanceados de una longitud dada. Así, el n -ésimo número de Catalan es igual al número de Lobb L _{0, n} . ^{[ 2 ]} Reciben su nombre de Andrew Lobb, quien los utilizó para dar una demostración inductiva sencilla de la fórmula para el n ^-ésimo número de Catalan. ^{[ 3 ]}

Los números de Lobb se parametrizan mediante dos enteros no negativos m y n, con n  ≥ m ≥ 0. ^El número de Lobb ( m , n ) L _{m , n} se expresa en términos de coeficientes binomiales mediante la fórmula    

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

Una expresión alternativa para el número de Lobb L _{m , n} es:

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

El triángulo de estos números comienza como (secuencia A039599 en el 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}}}$

donde la diagonal está

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

y la columna de la izquierda son los números catalanes.

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

Además de contar secuencias de paréntesis, los números de Lobb también cuentan las formas en que n  + m copias del valor +1 y n − m copias del valor −1 pueden organizarse en una secuencia de tal manera que todas las sumas parciales de la secuencia sean no negativas.   

En el teorema de la votación de Bertrand , publicado por primera vez por William Allen Whitworth en 1878 , la combinatoria de los paréntesis se reemplaza por el recuento de votos en una elección con dos candidatos. El teorema establece la probabilidad de que el candidato ganador vaya por delante en el recuento, dados los resultados finales conocidos para cada candidato.