Число Лобба

В комбинаторной математике число Лобба L m _{, n подсчитывает} количество способов, которыми n  +  m открывающих скобок и n  −  m закрывающих скобок могут быть расставлены для формирования начала допустимой последовательности сбалансированных скобок . ^[1]

Числа Лобба образуют естественное обобщение чисел Каталона , которые подсчитывают полные строки сбалансированных скобок заданной длины. Таким образом, n- е число Каталона равно числу Лобба L _{0, n} . ^[2] Они названы в честь Эндрю Лобба, который использовал их, чтобы дать простое индуктивное доказательство формулы для n- ^го числа Каталона. ^[3]

Числа Лобба параметризуются двумя неотрицательными целыми числами m и n, где n  ≥  m  ≥ 0. ( m ,  n ) ^-е число Лобба L _{m , n} задается через биномиальные коэффициенты по формуле

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

Альтернативное выражение для числа Лобба L _{m , n} имеет вид:

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

Треугольник этих чисел начинается как (последовательность A039599 в 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}}}$

где диагональ

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

а левый столбец - каталонские цифры

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

Помимо подсчета последовательностей скобок, числа Лобба также подсчитывают способы, которыми n  +  m копий значения +1 и n  −  m копий значения −1 могут быть организованы в последовательность таким образом, что все частичные суммы последовательности будут неотрицательными.

Комбинаторика скобок заменяется подсчетом бюллетеней на выборах с двумя кандидатами в теореме Бертрана о голосовании , впервые опубликованной Уильямом Алленом Уитвортом в 1878 году. Теорема устанавливает вероятность того, что победивший кандидат окажется впереди при подсчете голосов, учитывая известные окончательные результаты для каждого кандидата.