I have been trying to practice specific discrete math questions in my textbook and am having issues understanding how the terms are defined for a formula. Two examples that I do not understand.
(1) Find a recurrence relation for $C_n$, the number of ways to parenthesize the product of $n + 1$ numbers, $x_1, x_2, \ldots, x_n$, to specify the order of multiplication. e.g. $C_3 = 5$ there are five ways to parenthesize $x_0 \cdot x_1 \cdot x_2 \cdot x_3$ to determine the order of multiplication:
- $((x_0 · x_1) · x_2) · x_3$
- $(x_0 · (x_1 · x_2)) · x_3$
- $(x_0 · x_1) · (x_2 · x_3)$
- $x_0 · ((x_1 · x_2) · x_3)$
- $x_0 · (x_1 · (x_2 · x_3))$.
(2) Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five?
For the first one, I don't understand how to approach this kind of question other than to set one pair of brackets and set the other to be completely within it or completely outside of it. But I am stuck beyond that.
For the second problem, I know that you are supposed to find the number of bitstrings that end in $1$ or $10$ and then add them. However, I do not really understand why this is the case and how this formula is achieved and further, why the number of bitstrings with two consecutive zeros would be this number plus $2^{n-2}$? It doesn't make a lot of sense to me.
Any help understanding or pointing me toward resources would be great I would really like to understand this. Thank you.
We are trying to count the number of ways to parenthesize $x_1 \cdot \cdot \cdot x_n $. This number is $ C_n $. But we can rewrite this as $ x_1 \cdot (x_2 \cdot \cdot \cdot x_n )$. There are then $ C_{n-1} $ ways to parenthesize the stuff in the parentheses. But we can also rewrite the original product as $ (x_1 \cdot x_2) \cdot ( x_3 \cdot \cdot \cdot x_n ) $. Now there are $ C_2 $ ways to parenthesize the left and $ C_{n-2} $ ways to parenthesize the right. Keep going. Do you see how we might continue? We can also start with $ (x_1 \cdot x_2 \cdot x_3) \cdot (x_4 \cdot \cdot \cdot x_n)$ which admits $ C_3 \cdot C_{n-3} $ sub-parenthesizations. Continuing in this fashion, we can count all $ C_n $ ways of parenthesizing $ x_1 \cdot \cdot \cdot x_n $ in terms of the quantities $ C_1, \ldots, C_{n-1} $.