parentesi Combinazione con aggiunta

Question

Ho un interessante problema della combinazione e mi sono un po 'bloccato

Consente definire una funzione p (xn), che restituisce il numero di '()' per l'equazione x Ora x può essere solo nella forma x1 + x2 + x3 ... xn è definito questa funzione per n> = 2

Esempi:

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

p (x3) ​​= ((x1 + x2) + x3) e (x1 + (x2 + x3))

p (x4) =

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

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

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

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

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

e così su Avviso (x1 + (x2 + x3) + x4) non è un esempio valido ci deve essere uno() per ogni +

Ora, sto cercando di trovare una formula per P che determinare il numero di combinazioni Non sono sicuro se esiste una formula fissa o una definizione ricorsiva che dipende dai termini precedenti. Ragazzi, potete aiutarmi a capire la formula?

Answer 1

In sostanza si sta cercando di contare il numero di alberi unici di espressione binari in cui i nodi sono sommatorie e le foglie sono x ax _n. Chiamiamo questo numero P (n).

È possibile scegliere una delle somme n-1 come nodo radice. Scegliamo la k'th summation. Ci sono k variabili a sinistra della radice, quindi puoi organizzare il sottostruttura di sinistra in P (k) modi. Ci sono variabili n-k a destra, quindi la sottostruttura giusta può essere organizzata in modi P (n-k). Quindi, in totale, puoi organizzare l'albero in P (k) P (n-k) in modi diversi.

Dal momento che si può scegliere k liberamente da 1 a n-1, il numero totale con cui è possibile organizzare l'albero di espressione con n lascia è:

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

Come notato da @DSM nei commenti questa ricorrenza la relazione genera i numeri catalani. Esiste una soluzione di forma chiusa, ma è un po 'complicato derivare dalla formula di ricorrenza. È possibile trovare diverse prove della formula nel Wikipedia article for Catalan numbers. La soluzione è:

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