Anzahl der Möglichkeiten, richtig Klammer Anordnung

Question

Ich habe eine Zeit lang über dieses Problem nachzudenken:

Was die Anzahl der Möglichkeiten, richtig ist * Anordnen von 2 * n Klammer.
* Eine korrekt angeordnete Folge von Klammern hat eine gleiche Anzahl von offenen und geschlossenen Klammern an ihrem Ende und eine größere oder gleiche Menge an offenen Klammern als die geschlossenen Klammern in der gesamten Sequenz.

Zum Beispiel für n=3 gibt es 5 Möglichkeiten: ((())),()(()),()()(), (())(), (()()).

Ich habe daran gedacht, verschachtelte Klammern als Bäume darzustellen, kam aber nicht weit.

Answer 1

Ihr Beispiel entspricht der Anzahl der Dyck words, die mit Kombinatorik gezählt werden kann und zu Catalan number gleich: