Number of ways to insert parentheses between elements

Question

From Rosen's Discrete Mathematics and Its Applications, 3ed, chapter 8.1 p. 506-507:

...there are Ck ways to insert parentheses in the product x0 · x1 · · · · · xk

I would like to ask where this conclusion comes from. I am at a loss here. It feels that this proof does not give me the whole story. Thank you.

Answer 1

Rosen defines $C_n$ to be the number of ways of inserting parentheses in the product $x_0 \cdot x_1 \cdot x_2 \cdot \cdots \cdot x_n$, which has $n + 1$ factors. He then observes that one multiplication symbol remains outside all parentheses and supposes that it lies between $x_k$ and $x_{k + 1}$. If this occurs, then the number of ways to parenthesize the product $x_0 \cdot x_1 \cdot x_2 \cdot \cdots \cdot x_n$ is found by multiplying the number of ways of parenthesizing the $k + 1$ factors in the product $x_0 \cdot x_1 \cdot x_2 \cdot \cdots \cdot x_k$, which is $C_k$, by the number of ways of parenthesizing the $n - k$ factors in the product $x_{k + 1} \cdot x_{k + 2} \cdot x_{k + 3} \cdot \cdots \cdot x_n$, which is $C_{n - k - 1}$. Since $k$ can range from $0$ to $n - 1$, we obtain $$C_n = \sum_{k = 0}^{n - 1} C_kC_{n - k - 1} = C_0C_{n - 1} + C_1C_{n - 2} + \cdots + C_{n - 1}C_0$$

Answer 2

This is not a conclusion. It's the definition of $C_k$, the number of ways to insert parentheses into a product of $k+1$ numbers.

Answer 3

I'll first give a different example and then explain more about your example, if you have $5$ blue chairs and beside them $4$ red chairs, you want to distribute $5$ boys on the blue chairs and $4$ girls on the red ones. In how many ways can you do this?

To get the answer you multiply the number of ways to distribute the boys over the blue chairs by the number of ways to distribute the girls over the red chairs.

The same is done in your example.

The author assumed that the last product or multiplication that will be done is ofcourse between some 2 consecutive elements that he called $x_k$ and $x_{k+1}$

Now you have $k+1$ element in $x_0, ..., x_k$ (i.e. $C_k$ ways to distribute the paranthesis) and $n-k$ elements from $x_{k+1}, ..., x_n$ (i.e. $C_{n-k-1}$ ways to distribute the paranthesis), thus he multiplied them by each other similar to the above example.

Finally because this last product might be between any 2 elements (i.e. either between $x_0$ and $x_1$ or between $x_1$ and $x_2$ or ... or between $x_{n-1}$ and $x_n$) so he'll add them up (i.e. $C_n = \sum_{k = 0}^{n - 1} C_kC_{n - k - 1}$)