Let $(a_n)$ denote the number of ways to place parenthesis to multiply $n$ numbers $k_1,k_2\ldots k_n$. Find a recurrence relation for $ (a_n)$
I can't think of way to go about this.
If we break the product $k_1\cdot k_2 \cdot k_3 \cdots k_n$ into groups of size $i$ and $n-i$ then it can be bracketed in $a_i \cdot a_{n-i}$ ways
so final answer should be $a_1a_{n-1} + a_2\cdot a_{n-2} + \ldots a_{n-1}\cdot a_1 $. Does this makes sense?
Best Answer
knowing all previous $a_k$, the choice you have is where to put the last multiplication. It can be anywhere between $k_1$ and $k_n$ which correspond to $n-2$ possible location, let $i\in[1:n-1]$ be that position, then you have on the left $i$ elements and on the right $n-i$ elements, you know in how many ways you can put parenthesis on those, hence the result is : \begin{align*} a_n = \sum_{i=1}^{n-1} a_i a_{n-i} \end{align*}
You can compute these numbers using generating function. The generating function is \begin{align*} xa(x) &= \sum_{n=1}^{\infty} a_{n} x^{n}\\ &=x+\sum_{n=2}^{\infty}\sum_{i=1}^{n-1} a_i a_{n-i}x^{n}\\ &=x+\sum_{i=1}^{\infty} a_i x^i \sum_{n=i+1}^{\infty}a_{n-i}x^{n-i}\\ &=x+\sum_{i=1}^{\infty} a_i x^i \sum_{n=1}^{\infty}a_{n}x^{n}\\ &=x+(xa(x))^2 \end{align*} In other words \begin{align*} xa(x)^2-a(x) +1 = 0 \end{align*} this is the generating function of the Catalan numbers, the end of the proof is similar to the wikipedia page and you obtain : \begin{align*} a_n= \frac{1}{n} {2(n-1)\choose n-1} \end{align*}