Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

2 Answers 2

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

share|improve this answer
    
$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
1  
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
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.