In how many ways can the string A ∩ B – A ∩ B – A be fully parenthesized to…
2016
In how many ways can the string
A ∩ B – A ∩ B – A
be fully parenthesized to yield an infix expression ?
- A.
15
- B.
14
- C.
13
- D.
12
Attempted by 391 students.
Show answer & explanation
Correct answer: B
Answer: 14
Explanation:
Identify operands: the expression A ∩ B – A ∩ B – A contains the operands A, B, A, B, A, so there are 5 operands (n = 5).
A fully parenthesized infix expression with n operands has Catalan number C_{n-1} possible parenthesizations.
Compute the relevant Catalan number: for n = 5 use C4 = (1/(4+1)) * binom(8,4) = (1/5) * 70 = 14.
Therefore the expression can be fully parenthesized in 14 distinct ways.