CODEWITHSUNDEEP
algorithmmathlanguage-agnosticcombinatoricscatalan
Arvid Nyman
Arvid Nyman

Reputation: 133

Number of ways of correctly arranging parenthesis

I've been thinking for a while about this problem:

What's the number of ways of correctly* arranging 2*n parenthesis.
*A correctly arranged sequence of parenthesis has an equal number of open and closed parenthesis at its end and a larger or equal amount of open parenthesis than the closed ones throughout the sequence.

For example, for n=3, there are 5 ways: ((())), ()(()), ()()(), (())(), (()()).

I've been thinking of representing nested parenthesis as trees, but didn't get far.

Upvotes: 10

Views: 4032

Answers (1)

Salvador Dali
Salvador Dali

Reputation: 222761

Your example equivalent to the number of Dyck words, which can be counted with combinatorics and will be equal to Catalan number:

enter image description here

Upvotes: 14

Related Questions