Number of ways of correctly arranging parenthesis

Question

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.

Knuth 4a has a paragraph about Catalan numbers. – wildplasser Dec 21 '15 at 22:46 — wildplasser, Dec 21 '15 at 22:46
Any link to a good combinatorics book? – Arvid Nyman Dec 22 '15 at 21:37 — Arvid Nyman, Dec 22 '15 at 21:37

score 12 · Accepted Answer · answered Dec 21 '15 at 21:00

12

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

answered Dec 21 '15 at 21:00

Salvador Dali

214,103
147
703
753

Catalan is untaught stuff... Thank you! – Arvid Nyman Dec 21 '15 at 21:14

Number of ways of correctly arranging parenthesis

1 Answers1