Ilość sposobów aranżacji prawidłowo nawias

Question

Myślałem przez chwilę o tym problemie:

Jaka jest szereg sposobów aranżacji poprawnie * 2 * n nawiasach.
* Poprawnie ułożona sekwencja nawiasów ma taką samą liczbę otwartych i zamkniętych nawiasów na końcu i większą lub równą liczbę otwartych nawiasów niż zamkniętych w całej sekwencji.

Na przykład dla n=3 istnieją 5 sposoby: ((())),()(()),()()(), (())(), (()()).

Zastanawiam się nad reprezentowaniem nawiasu zagnieżdżonego jako drzewa, ale nie zajdą daleko.

Answer 1

Twój przykład odpowiednik liczby Dyck words, który może być liczony z kombinatoryki i będzie równa Catalan number: