$C_n$, the number of ways to parenthesize the product of n+1 num-bers,$x_0·x_1·x_2· ··· ·x_n$, to specify the order of multiplication.
"To develop a recurrence relation for $C_n$, we note that however we insert parentheses
in the product $x_0·x_1·x_2· ··· ·x_n$, one “·” operator remains outside all parentheses, namely,
the operator for the final multiplication to be performed. [For example, in ($x_0·(x_1·x_2))$·,
it is the final “·”, while in($x_0·x_1)·(x_2·x_3)$ it is the second “·”.] This final operator appears
between two of the n+1 numbers, say, $x_k$ and $x_{k+1}$. "
I understand the above, but from here on, I have no clue what is going on, and I was wondering if there was any other way to word this explanation to explain it because I don't understand it at all:
"There are $C_k$ $C_{n−k−1}$ ways to insert
parentheses to determine the order of the n+1 numbers to be multiplied when the final op-erator appears between $x_k$ and x$_{k+1}$, because there are $C_k$ ways to insert parentheses in the
product $x_0·x_1· ··· ·x_k$ to determine the order in which these k+1 numbers are to be multi-plied and $C_{n−k−1}$ ways to insert parentheses in the product $x_{k+1}·x_{k+2}· ··· ·x_n$ to determine the order in which these n−k numbers are to be multiplied."
I don't understand….at all. I think the part I don't get is the $C_{n−k−1}$ part, and I just don't know if maybe this explanation is not good or I simply just don't understand it but I really really really do not understand this
Best Answer
The $k$ is an intermediate value, somewhere in the middle. It's split up this way to handle a reasonable general case: that you don't parenthesize the whole expression. If it were possible to do this, then $C_k$ would be ill-defined because you could put as many sets of parentheses around a particular expression as you wanted.
So one multiplication is outside any parentheses, and that location is determined by the value $k$ where $0 \leq k < n$:
$$x_0 \times x_1 \times x_2 \times ... \times x_{k-1} \times x_k \times x_{k+1} \times ... \times x_n.$$
So there are $C_k$ ways to parenthesize the terms from $x_k$ all the way left, and $C_{n-(k+1)} = C_{n-k-1}$ ways to parenthesize the terms $x_{k+1}$ all the way right. The total number of ways is the product of these two numbers.
Hope that helps.