Question

What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?

(a) nth catalan number

(b) n factorial

(c) n cube

(d) n square

I have been asked this question during an interview.

I'd like to ask this question from Counting Boolean Parenthesizations in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right answer is (a) nth catalan number

Best explanation: The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.