How many ways to compute a polynomial expression? Hi guys is there an algorithm or procedure that could tell me how many and what are the ways to compute an algebraic expression?
Just to make a stupid example...
$$x + y + z = (x + y) + z = x + (y + z) = (x + z) + y = ...$$ 
For polynomial bivariate (other example...)
$$xy + yz = (x + z)y$$ etc...
$$x^2 y + z = x (xy) + z$$
I'm interested to know if there is an algorithm that could give an answer somehow.
(I don't know where I should put such question...)
 A: A lower bound
would be 
to construct a syntax tree
of the expression
and then
count the number of ways
of traversing the tree.
A: The question is ambiguous. It depends on what is meant by "compute". It really is a matter of syntax. For example, in the lambda calculus, there are a number of reductions that can be done to terms, see: lambda reductions. But the rules for reduction are well defined there. Whereas here, we do not know what the rules are. Without any constraints, there are an infinite number of ways to reduce a term e.g.
$$(x + y) \rightarrow \frac22(x + y) \rightarrow \frac22x + \frac22y \rightarrow \frac22(\frac22x + \frac22y) \rightarrow \frac44x + \frac22(\frac22y) \rightarrow \frac44x + \frac44y \rightarrow \frac44(x + y) \rightarrow (x + y)$$
A computer could really do all these operations and legally end up with the same term. Clearly this would be bizarre and wasteful, but it would not affect the result of the evaluation. There are clearly an infinite number of these computations. So the trivial answer to the question, which does not enforce any constraints on the nature of the computations, is that the number of computations is unbounded.
On the other hand, it seems there must be a "sensible" notion of computation, where work isn't wasted. For this, there is still a great deal of ambiguity to overcome. For example, if $x$ and $y$ are matrices, we can't swap the order of multiplication $xy$ to $yx$. So before we answer this question, what we need is an axiomatic system of reductions/rewrites like the lambda calculus that gives us rules for exactly how to evaluate terms. Only then will we be (possibly) equipped to count the number of computations.
