# Recursive combinatorics with numbers and operators

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.

-
This question doesn't seem complete. What is $f$ supposed to be? The number of possible strings of length $n$? – Ben Millwood Feb 23 '13 at 21:49
Thanks for your remark, clarified. – SyBer Feb 24 '13 at 8:54

OK, consider a valid sequence. It is either:

• Just a 0
• Just a 1
• A valid sequence, followed by 0 or 1
• A valid sequence, followed by an operator $+$, $-$, $*$, $/$, and one of 0 or 1

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)

-
Thanks for the effort, though joriki answer did the click for me. – SyBer Feb 26 '13 at 12:14
Question, why we don't take into account the case of: A valid sequence, followed by one of 0 or 1, and one of 0 or 1 – SyBer Mar 2 '13 at 20:21
@SyBer, it is included: There are 2 ways of adding a digit (0, 1), and that increases the length by 1; there are 8 ways of adding an operator and a digit (+, +, *, / with 0, 1), the length increases by 2. – vonbrand Mar 2 '13 at 20:24
That's exactly my question (probably of whole recurrence idea) - if it included in (n-1), it will be included in following (n-i)? I.e. the only option to take a case with different situation? What about cases where the situation would be the same (i.e. string of only digits with no limitations)? Thanks for any clarification on this. – SyBer Mar 4 '13 at 12:39
@SyBer, in this case all valid sequences end in 0 or 1. To extend some sequence of length $k$, y append a 0 or 1 (2 possibilities) giving a sequence of length $k + 1$, or an operator and a 0 or 1 (8 possibilities in all) and length $k + 2$. Now turn the argument around: How can a valid sequence of length $n$ be made? From the above, in 2 ways from a valid sequence of length $n - 1$, and in 8 ways from a valid sequence of length $n - 2$. – vonbrand Mar 4 '13 at 13:20

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)$.

-
Thanks for the answer, it specifically pointed I misunderstood the recursive concept, by treating it like a recursive function processing input from the start, rather then a decreasing series. – SyBer Feb 26 '13 at 12:13
I've reviewed this question again, and see I still not fully get it - namely, why we don't take into account the case of f(n-2),0/1,0/1 (digit and digit again)? – SyBer Mar 2 '13 at 20:20
@SyBer: I don't understand what you mean by referring to that as a "case". I distinguished two exhaustive and mutually exclusive cases, strings ending in a digit and strings ending in an operator, and I counted the two cases and added the results. If by your notation you're referring to an arbitrary string of length $n-2$ followed by two digits, those are being counted correctly in the first case, the strings ending in a digit, of which there are $2f(n-1)$. It's also true that there are $4f(n-2)$ strings ending in two digits, but that's irrelevant to the case distinction I made. – joriki Mar 2 '13 at 22:00
Sorry - missed term from original question, saying that strings also can't end on an operator (though the answer remains the same). The bit you mentioning: "arbitrary string of length n−2 followed by two digits, those are being counted correctly in the first case" - this the bit I don't fully understand (probably as part of whole recurrence idea): if I counted the (n-1) ending on digit, why I should not count it again for (n-2) - but only the case of digit/operator? I.e. does counting something at (n-1), automatically counts all subsequent (n-i), and counting it again will be a duplicate? – SyBer Mar 4 '13 at 12:36
@SyBer: Using "cases" amounts to taking the set $S$ you are counting and writing it as a disjoint union of subsets of $S$. The union of the subsets being $S$ means that you have covered every possibility once, while the subsets being disjoint means you haven't double counted anything. In joriki's case, he decomposed the set $S$ of valid strings into two subsets: (1) those that end with a digit; and (2) those that end with an operator. It is clear (I hope) that this the set of all valid strings is the disjoint union of these two subsets. So it would be incorrect to (continued below) ... – Michael Joyce Mar 4 '13 at 12:56