Say we have an expression: $$a_0+a_1+\cdots+a_{n-1}$$ how many ways can we take parentheses? (as I understand, how many evaluation orders) I was thinking if there's $n$ number, 1st step we will need to combine any two consecutive and then we are left with $n-1$ numbers and we repeat, so I got a solution: $(n-1)!$ and I tried to verify with a simple $3+4+5$ => $((3+4)+5)$, $(3+(4+5))$ = $(3-1)!$
However I was told in this MIT Algorithm courses on DP(parenthsization) that the number should be $4^n$, but it doesn't provide a proof...so I wonder if anyone might know its computed? and why is it different from mine?