Question

Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

(a) n factorial

(b) n square

(c) n cube

(d) nth catalan number

I had been asked this question in a job interview.

My doubt is from Counting Boolean Parenthesizations in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

The correct choice is (d) nth catalan number

To explain: The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.