Номер Лобба

В комбинаторной математике 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} задается через биномиальные коэффициенты по формуле

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

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

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

Треугольник этих чисел начинается как (последовательность A039599 в OEIS )

{\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}}

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

L_{n,n}=1,

а левый столбец — каталонские номера.

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

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

Подсчет бюллетеней

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

Ссылки

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

[1] Коши, Томас (март 2009 г.). «Обобщение Лоббом проблемы каталонских скобок». Математический журнал колледжа . 40 (2): 99–107. дои : 10.4169/193113409X469532 .

[2] Коши, Томас (2008). Каталонские номера с приложениями . Издательство Оксфордского университета. ISBN 978-0-19-533454-8 .

[3] Лобб, Эндрю (март 1999 г.). «Получение n- го каталонского числа». Математический вестник . 83 (8): 109–110. дои : 10.2307/3618696 . JSTOR 3618696 . S2CID 126311995 .

[1]

[2]

[3]