|
I have the following question that I have difficulty to grasp: A string from 0,1,+,-,*,/ There are 2 rules: 1) string must start and end with a number. 2) string must not have two operators one after another. The lecturer answer is f(n)=2f(n-1)+8f(n-2), while f(n) is the number of possible strings of length n, answering on said rules. While 2f(n-1) is clear 8f(n-2) is not, as it creates possible duplications. Any idea? Thanks. |
|||||
|
|
A string of length $n$ can end either in a digit or in an operator. If it ends in a digit, it is the concatenation of any string of length $n-1$, of which there are $f(n-1)$, with any digit, of which there are $2$, which accounts for $2f(n-1)$. If it ends in an operator, it is the concatenation of any string of length $n-2$, of which there are $f(n-2)$, with any digit, of which there are $2$, and any operator, of which there are $4$, which accounts for $4\cdot2\cdot f(n-2)=8f(n-2)$. |
|||||||||||
|
|
OK, consider a valid sequence. It is either:
Pulling the different alternatives together: $$ f(n + 2) = 2 f(n + 1) + 8 f(n) \quad f(0) = 1, f(1) = 2 $$ Can even solve explicitly: Define $F(z) = \sum_{n \ge 0} f(n) z^n$, using properties of ordinary generating functions: $$ \frac{F(z) - f(0) - f(1) z}{z^2} = 2 \frac{F(z) - f(0)}{z} + 8 F(z) $$ I.e.: $$ F(z) = \frac{1}{1 - 2 z - z^2} $$ By partial fractions this splits into two geometric series, unfortunately somewhat messy: $$ F(z) = \frac{1}{2^{3/2} (1 + \sqrt{2})} \cdot \frac{1}{1 + z(1 + \sqrt{2})^{-1})} - \frac{1}{2^{3/2} (1 - \sqrt{2})} \cdot \frac{1}{1 - z(1 + \sqrt{2})^{-1})} $$ From here: $$ f(n) = \frac{1}{2^{3/2} (1 + \sqrt{2})} (\sqrt{2} - 1)^{-n} - \frac{1}{2^{3/2} (1 - \sqrt{2})} (\sqrt{2} + 1)^{-n} $$ (I hope I didn't mistype what Maxima gave) |
|||||||||||
|
