[Math] Number of ways to parenthesize to yield an infix expression

catalan-numberscombinatoricsdiscrete mathematics

In how many ways can the string
$A ∩ B – A ∩ B – A$
be fully parenthesized to yield an infix expression?

  1. $15$
  2. $14$
  3. $13$
  4. $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:

$C_n$ is the number of different ways $n+1$ factors can be completely parenthesized (or the number of ways of associating $n$ applications of a binary operator).

The correct answer is $C_4=14$.

Related Question