Numer Lobba

W matematyce kombinatorycznej liczba Lobba L _{m , n} zlicza liczbę sposobów , na jakie n + m nawiasów otwartych i n - m nawiasów zamkniętych można ułożyć w celu utworzenia początku ważnej sekwencji zrównoważonych nawiasów .

Liczby Lobba stanowią naturalne uogólnienie liczb katalońskich , które zliczają liczbę pełnych ciągów zrównoważonych nawiasów o określonej długości. Zatem n -ta liczba katalońska równa się liczbie Lobba L _{0, n} . Zostały nazwane na cześć Andrew Lobba, który użył ich do prostego indukcyjnego dowodu wzoru na n ^-tą liczbę katalońską.

Liczby Lobb są sparametryzowane przez dwie nieujemne liczby całkowite m i n , przy czym n ≥ m ≥ 0. ( m , n ) ^ta liczba Lobb L _{m , n} jest wyrażona jako współczynniki dwumianowe za pomocą wzoru

${\ Displaystyle L_ {m, n} = {\ Frac {2m + 1} {m + n +1}}{\binom {2n}{m+n}}\qquad {\text{dla}}n\geq m\geq 0.}$

Alternatywnym wyrażeniem dla liczby Lobba L _{m , n} jest:

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

Trójkąt tych liczb zaczyna się jako (sekwencja A039599 w OEIS )

${\ Displaystyle {\ rozpocząć {tablica} {rrrrrr} 1 \\ 1 i 1 \\ 2 i 3 i 1 \\ 5 i 9 i 5 i 1 \\ 14 i 28 i 20 i 7 i 1 \\ 42 i 90 i 75 i 35 i 9 i 1 \ \\end{tablica}}}$

gdzie jest przekątna

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

a lewa kolumna to liczby katalońskie

${\ Displaystyle L_ {0, n} = {\ Frac {1} {1 + n}} {\ binom {2n} {n}}.}$

Oprócz zliczania sekwencji nawiasów, liczby Lobb zliczają również liczbę sposobów, na jakie n + m kopii wartości +1 i n - m kopii wartości -1 można ułożyć w sekwencję w taki sposób, że wszystkie częściowe sumy sekwencji są nieujemne.

Liczenie głosów

Kombinatorykę nawiasów zastępuje się liczeniem kart do głosowania w wyborach z dwoma kandydatami w twierdzeniu o głosowaniu Bertranda , opublikowanym po raz pierwszy przez Williama Allena Whitwortha w 1878 r. Twierdzenie to określa prawdopodobieństwo , że zwycięski kandydat ma przewagę w liczeniu, biorąc pod uwagę znane końcowe wyniki dla każdego kandydata .