Nawiasy skojarzone z dodatkiem

Question

Mam ciekawy problem kombinacji i jestem trochę zatrzymany

Pozwala zdefiniować funkcję p (xn), która zwraca liczbę „()” o równaniu x x Teraz może być tylko w postaci x1 + x2 + x3 ... Xn funkcja ta jest określona przez n> = 2

Przykłady:

P (x2) = (x1 + x2) = 1

P (x3) ​​= ((x1 + x2) + x3) i (x1 + (x2 + x3))

P (4x) =

((x1 + x2) + (x3 + x4))

(((x1 + x2) + x3) + x4)

((x1 + (x2 x3)) + x4)

(x1 + ((x2 x3) + x4))

(x1 + (x2 (x3 + x4)))

itd na Uwaga (x1 + (x2 + x3) + x4) nie jest prawidłowym przykładem musi być jeden() dla każdego +

Teraz próbuję wymyślić formułę dla P, która będzie określ liczbę kombinacji Nie jestem pewien, czy istnieje ustalona formuła lub rekurencyjna definicja, która zależy od poprzednich warunków. Czy możecie mi pomóc zrozumieć tę formułę?

Answer 1

Zasadniczo szukasz policzyć liczbę unikalnych drzew binarnych ekspresyjnych, gdzie węzły są sumowania i liście są x do x _n. Nazwijmy ten numer P (n).

Możesz wybrać dowolne z sumacji n-1 jako węzeł główny. Wybierzmy sumę kth. Po lewej stronie katalogu głównego znajduje się k zmiennych, więc możesz organizować lewe poddrzewo w sposób P (k). Po prawej stronie są zmienne n-k, więc odpowiedni poddrzewo może być zorganizowane w sposób P (n-k). Zatem w sumie możesz uporządkować drzewo w P (k) P (n-k) na różne sposoby.

Ponieważ można wybrać dowolnie k od 1 do n-1, łączna liczba z którym można zorganizować drzewa wyrażenie z n liście jest:

P(n) = P(1)P(n-1) + P(2)P(n-2) + ··· + P(n-2)P(2) + P(n-1)P(1) 

Jak zauważył @DSM w komentarzach Nawrót relacja generuje liczby katalońskie. Istnieje rozwiązanie o zamkniętej formie, ale jest to trochę trudne, aby wyprowadzić z formuły powtarzania. Możesz znaleźć kilka dowodów na wzór w Wikipedia article for Catalan numbers. Rozwiązaniem jest:

P(n) = C(2n,n)/(n+1)    where C(n,k) = n!/(k!(n-k)!)