Numero di alberi binari

[vl4dster]

provare che il numero di alberi binari con n vertici e' $b_{n}=\sum_{k=0}^{n-1}b_{k}b_{n-1-k}$

non riesco a capire qual'e' il ragionamento che sta dietro a questa relazione... l'unica cosa che vedo e' che dalle $n!$ permutazioni dei nodi bisogna togliere le permutazioni che danno una struttura uguale ad un'altra... se qualcuno mi aiuta...

[vl4dster]

Sia $T$ un albero binario con $n$ nodi, isoliamo la radice, ora consideriamo i due sottoalberi destro-sinistro: se quello a sinistra ha $k$ nodi allora quello a destra ne ha $n-1-k$. gli alberi possibili a sinistra sono dunque $b_{k}$, quelli a destra $b_{n-1-k}$ per un totale di $b_{k}b_{n-1-k}$. Cosa vale $k$? a seconda di come scelgo la struttura a sinistra $k$ puo' andare da $0$ a $n-1$, dunque ho la relazione sopra.