Prove that number of parenthesizing is Catalan number

432 Views Asked by At

Consider a product of 4 numbers, abcd. It can be “parenthesized” in 5 ways: $((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d),$ and $ a(b(cd))$. Prove that the number of such parenthesizings of a product of n numbers is the Catalan number $b_{n-1}$.

I don't know how to begin.