# 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?

-
This question is too broad - Operation set isn't defined, nor is it clear where did you get numbers such as $n-2$ from. But in general I believe mathematics isn't yet ready for such problems... – Guest 86 Feb 11 '13 at 13:33
I disagree with Guest 86. The operation set is explicitly given in the question, and the numbers like $n-2$ clearly represent repetitions of a certain number (like $n-3$) of the same operation (addition in the second example, multiplication in the fourth). – Andreas Blass Feb 11 '13 at 13:41
The question is quite clear and well-defined, for example $3x_2$ is $x_2+x_2+x_2$, or two successive additions (two plus signs), in the same fashion $(n-2)$ times a number is $(n-3)$ additions. Does this clarify more the essence of the question? – A.P. Feb 11 '13 at 14:58
Best I got is $F\left(1\right)=2$ and $F\left(m\right)=\sum_{i=1}^{m}\left(\begin{array}{c}i+n-1\\ i\end{array}\right)F\left(m-i\right)$ with $F\left(n\right)$ as the answer. – zaarcis Feb 11 '13 at 15:45
$F(1)$ does not have meaning because if you mean that $1$ in your function argument represents number of numbers on which we operate, so that we only have $x_1$ then with n successive operations which can be addition or multiplication we can get these numbers: $2x_1, 3x_1, ..., (n+1)x_1, (x_1)^2, (x_1)^3, ..., (x_1)^{n+1}$, so $F(1;n)=2n$ – A.P. Feb 11 '13 at 15:54

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

-
$F(n,3)=\frac{n(n+1)(5n^2+9n+6)}{8}$ must be wrong. When $n=1$ it gives $5$, but there is $8$ possibilities: $$x_{1}+x_{1}+x_{1}+x_{1}=4x_{1}$$ $$\left(x_{1}+x_{1}+x_{1}\right)\cdot x_{1}=3x_{1}^{2}$$ $$\left(x_{1}+x_{1}\right)\cdot x_{1}+x_{1}=2x_{1}^{2}+x_{1}$$ $$\left(x_{1}+x_{1}\right)\cdot x_{1}\cdot x_{1}=2x_{1}^{3}$$ $$x_{1}\cdot x_{1}+x_{1}+x_{1}=x_{1}^{2}+2x_{1}$$ $$\left(x_{1}\cdot x_{1}+x_{1}\right)\cdot x_{1}=x_{1}^{3}+x_{1}^{2}$$ $$x_{1}\cdot x_{1}\cdot x_{1}+x_{1}=x_{1}^{3}+x_{1}$$ $$x_{1}\cdot x_{1}\cdot x_{1}\cdot x_{1}=x_{1}^{4}$$ – zaarcis Feb 11 '13 at 22:19
Also with $F\left(n,2\right)=\frac{n\left(n+1\right)\left(5n+4\right)}{6}$. If $n=1$, it gives $3$, but there's $4$ possible values: $$x_{1}+x_{1}+x_{1}=3x_{1}$$ $$\left(x_{1}+x_{1}\right)\cdot x_{1}=2x_{1}^{2}$$ $$x_{1}\cdot x_{1}+x_{1}=x_{1}^{2}+x_{1}$$ $$x_{1}\cdot x_{1}\cdot x_{1}=x_{1}^{3}$$ If I misunderstood something, let me know. – zaarcis Feb 11 '13 at 22:42
I dont think brackets are allowed. If they are allowed the answer is of course different. My answer assumes that brackets are not allowed, so you cant have $(x_1+x_1)*x_1$, for example. – Ivan Loh Feb 12 '13 at 2:05
I think... maybe "my problem" with allowed brackets always gives bigger numbers and so can be used for upper bound of your problem? :P – zaarcis Feb 12 '13 at 2:27
Ok, then maybe you should edit the qn to explicitly make this clear. A good example would be the one mentioned above, $(x_1+x_1)*x_1$, which is not counted as a possibility for your question. – Ivan Loh Feb 12 '13 at 13:02

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.

-
I understand your point of view, now I have changed the question so if you know something at least about $F(2,m)$ you can share it here, and that commutativity problem, what is problem there? – A.P. Feb 11 '13 at 16:48
@A.P.: the commutivity problem is that $x_2+x_1$ and $x_1+x_2$ yield the same result. My upper bound counts them as distinct. To get a solid answer to your question one has to figure out all the patterns that you can prove are equal, which I think is hard. – Ross Millikan Feb 11 '13 at 16:51
I know what he meant when he mentioned the commutivity problem but I do not see easily why it is so hard to subtract the combinations that yield same results, can we get at least upper bound for the number of duplicates if all $x_i$, $i=1,2,...,n$ are different? And would you like to tell of what form is your upper bound that bounds the number of combinations where every two combinations are distinct? – A.P. Feb 11 '13 at 16:57
The same bound would give $F(n,m) \leq n(2n)^m$. I agree that its hard to get a general answer, as $F(1,m)$ is already the partition function, which doesnt have a nice expression. (It does have a nice generating function, and satisfies a recurrence which can be used to calculate values though) – Ivan Loh Feb 11 '13 at 16:57