Counting combinations If we have $n$ different numbers from the set $\mathbb  N$ what is the maximum possible number of numbers that we can contruct from these numbers by performing $m$ successive operations, where operation is addition or multiplication? To be more precise about the problem I will clarify it further with some examples, thus, if we have $x_1,x_2,...,x_n$ and $m=n$ then some of the possible combinations are:
$2x_1+x_2+...+x_n=x_1+x_1+x_2+...+x_n$
$(n-2)x_1+3x_2=\underbrace{x_1+x_1+ \ldots +x_1}_{n-2 \, \text{terms}}+x_2+x_2+x_2$
$x_1+x_2+(x_{n-1})^{n-1}=x_1+x_2+\underbrace{x_{n-1}*x_{n-1}* \ldots *x_{n-1}}_{n-1 \, \text{terms}}$
$(x_3)^3+ (x_n)^{n-2}=x_3*x_3*x_3+\underbrace{x_{n}*x_{n}* \ldots *x_{n}}_{n-2 \, \text{terms}}$
$(x_1)(x_2)^n=x_1*\underbrace{x_2*x_2* \ldots *x_2}_{n \, \text{terms}}$
If we denote the dependence of maximum possible number of numbers that can be constructed from $n$ numbers and $m$ successive operations as $F(n,m)$ can we, if not set the general expression $F(n,m)$ at least solve some particular cases as $F(2,m)$?
For instance, $F(2,1)=6$, combinations are $x_1+x_1 , x_2+x_2, x_1+x_2, x_1x_2, (x_1)^2,(x_2)^2 $
EDIT:
If it is hard to find exact expression for general case (and it surely looks like it is) or even for the case $F(2,m)$ what is the best upper bound that you can create for this problem?
 A: Note: The OP has clarified that brackets are not allowed. In other words, we have $m+1$ terms and $m$ successive operations in between, so terms like $(x_1+x_1)*x_1$ are not counted as a possibility. (We take it as $x_1+x_1*x_1=x_1+x_1^2$ instead)
In general, if you fix $m$, then $F(n,m)$ is a polynomial of degree $m+1$ with respect to $n$. I have no general formula to get the coefficients though, but at least the trivial bound provided by @Ross Millikan is a polynomial with the same degree, though the leading coefficient of $2^m$ is too large. I will prove a non-trivial bound $F(n,m) \leq p(m+1)n^{m+1}$, where $p(x)$ is the partition function.
To show the above result, let $c_i$ be the number of products with $i$ terms. Each product with $i$ terms uses $i-1$ multiplication operations, giving a total of $\sum\limits_{i=1}^{m+1}{(i-1)c_i}$. Also there are $\sum\limits_{i=1}^{m+1}{c_i}-1$ addition operations, so $\sum\limits_{i=1}^{m+1}{ic_i}=m+1$
Now the number of different products with $i$ terms is simply $\binom{i+n-1}{i}$. To see this, simply let $b_j$ be the number of $x_j$ in the product, then this is equivalent to the number of non-negative integer solutions to $\sum\limits_{j=1}^{n}{b_j}=i$.
The number of ways to have $c_i$ such products is simply $\binom{c_i+\binom{i+n-1}{i}-1}{c_i}$. To see this, simply number the products, then $a_j$ be the number of times the jth product appears, then this is equivalent to the number of non-negative integer solutions to $\sum\limits_{j=1}^{\binom{i+n-1}{i}}{a_j}=c_i$.
Thus the total number of combinations with fixed $c_i$ is $\prod\limits_{i=1}^{m+1}{\binom{c_i+\binom{i+n-1}{i}-1}{c_i}}$.
Thus
$$F(n,m)=\sum\limits_{\sum\limits_{i=1}^{m+1}{ic_i}=m+1}{\prod\limits_{i=1}^{m+1}{\binom{c_i+\binom{i+n-1}{i}-1}{c_i}}}$$
This is indeed a polynomial in $n$ with degree $m+1$. Note that all coefficients are positive.
Small cases: $F(n,1)=n(n+1), F(n,2)=\frac{n(n+1)(5n+4)}{6}, F(n,3)=\frac{n(n+1)(5n^2+9n+6)}{8}$.
When $n=1, \binom{i+n-1}{i}=1$, so $\prod\limits_{i=1}^{m+1}{\binom{c_i+\binom{i+n-1}{i}-1}{c_i}}=1$, so $F(1,m)=p(m+1)$. Now $g(n)=\frac{F(n,m)}{n^{m+1}}$ is a decreasing function of $n$, so $F(n,m) \leq F(1,m)n^{m+1}=p(m+1)n^{m+1}$.
If one notices that $F(n,m)$ always has $(n+1)$ as a factor (this is relatively easy to show), and that $F(n,m)=(n+1)P(n)$ where $P(n)$ is a polynomial with degree $m$ and positive coefficients, then the same method gives the slightly improved bound $F(n,m) \leq \frac{F(1,m)}{2}n^{m}(n+1)=\frac{p(m+1)}{2}n^{m}(n+1)$.
A: A simple upper bound is that you choose a variable to start with ($n$ choices), then each operation gives $2n$ possibilities, as you can choose $n$ different variables and $2$ operations, so the total is $n(2n)^n$.  The hard part is counting the number that must be equal due to commutivity.  If you choose the $x_i$ properly you should be able to avoid coincidences that don't have to be true.  If you count the $n=3$ case by hand you might get something you could look up in OEIS-it will be large enough there won't be too many hits.
