I'm reading a book on functional programming (no need to know about it for the question) and a problem form it I'm having trouble with is to count all the ways an expression can be reduced. For example if
double x = x + x
then the evaluation of double (3 + 4) can happen first by evaluating the $(3+4)$ (which can be done in one way and produces $7$) or we can first evaluate the function and then substitute:
double (3 + 4) ==> (3 + 4) + (3 + 4)
==> 7 + (3 + 4)
==> 7 + 7
==> 14
Another way would be to first evaluate the second parenthesis in step 2, so we have three in total. The question is how many ways are there to evaluate double (double (3 + 4))?
This is what I managed to come up with: based on the fact that the unnested expression can be done in 3 ways, we have two further choices: We could first evaluate it and then we have collapsed the problem to the initial one, so the total number would have to be $3^2$ ways; or we can first evaluate the function and reduce to
(double (3+4)) + (double (3+4))
which can be done in another $3^2$ ways so the total would be $18$. I feel like I might be missing something, though. For example, we could start evaluating the inside expression and then suddenly evaluate the function, so we don't stick with either method till the end, so this should produce different ways to do it. Any thoughts on this would be appreciated.