In how many ways can the string
$A ∩ B – A ∩ B – A$
be fully parenthesized to yield an infix expression?
- $15$
- $14$
- $13$
- $12$
My attempt:
Somewhere it explained as:
Number of ways to parenthesize operands using catalan number, i.e.,
$C((2n), n)/(n+1) = \color{red}{C(10, 5)/6} = 14$. Well he commented that he assumed $n$ is total number of $\color{red}{\text{operands}}$, but he computed wrong answer $\color{red}{\text{14? now it should be 42.}}$
I think $n$ is total number of $\color{green}{\text{Operators}}$? Can you explain it, please?
Best Answer
You are correct; this is an off-by-one error. See Catalan numbers on Wikipedia:
The correct answer is $C_4=14$.