Номер вестибюля

В комбинаторной математике число Лобба 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 могут быть организованы в такую ​​последовательность, что все частичные суммы последовательности неотрицательны.

Ссылки [ править ]