In how many ways can the string A ∩ B – A ∩ B – A
In how many ways can the string
A ∩ B – A ∩ B – A
be fully parenthesized to yield an infix expression?
Show answerHide answer
Correct answer: (B) 14
Explanation
The number of ways to fully parenthesize an expression with n operators is the Catalan number C(n) = (1/(n + 1)) × ²ⁿCₙ. Here the number of operators is n = 4, so C(4) = (1/5) × ⁸C₄ = (1/5) × 8!/(4! 4!) = 70/5 = 14. Note: All operators work as nodes of a binary tree.