Generation of Combinatorial Objects · Parenthesis Sequences

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

A parenthesis sequence is a sequence of opening and closing parentheses. Informally, such a sequence is called valid if each opening parenthesis can be matched with a closing one. Examples of valid parenthesis sequences:

\(\texttt{()}\)

\(\texttt{(())}\)

\(\texttt{()()}\)

\(\texttt{(()(()))()}\)

Examples of invalid parenthesis sequences:

\(\texttt{(}\)

\(\texttt{)(}\)

\(\texttt{(()())(()}\)

\(\texttt{(()(()())))(()}\)

Formally, a valid parenthesis sequence can be defined as follows. The balance of a parenthesis sequence is the difference between the number of opening and closing parentheses. Then, a sequence is called valid if its balance is zero and the balance of any of its prefixes is non-negative.