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

В комбинаторная математика, то Номер вестибюля L_м,п подсчитывает количество способов, которыми п + м открытые скобки и п − м закрывающие скобки могут быть расположены в начале допустимой последовательности сбалансированные скобки.^[1]

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

Номера Лобба параметризуются двумя неотрицательными целые числа м и п с п ≥ м ≥ 0. (м, п)^th Номер вестибюля L_м,п дается с точки зрения биномиальные коэффициенты по формуле

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

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

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

Рекомендации

1. Коши, Томас (март 2009 г.). «Обобщение Лоббом проблемы скобок Каталонии». Математический журнал колледжа. 40 (2): 99–107. Дои:10.4169 / 193113409X469532.
2. Коши, Томас (2008). Каталонские номера с приложениями. Издательство Оксфордского университета. ISBN  978-0-19-533454-8.
3. Лобб, Эндрю (март 1999). "Получение пй каталонский номер ". Математический вестник. 83 (8): 109–110.