# Number of combinations of $k$ numbers using arithmetic operations

What is the maximum number of positive rational values that can be obtained by combining $k$ positive integers using only addition, subtraction, multiplication, division, and parentheses? Assume that each value must be used once and only once.

I believe that the sequence starts as follows: 1, 5, 47, 733, 15907, 443825.

The second term is 5 because we can form 5 different positive numbers from $\{a, b\}$ if $a > b$:

$$a+b,\ \ a-b,\ \ a\cdot b,\ \ \frac{a}b,\ \ \frac{b}a\ .$$

• Are you allowing parentheses, e.g., $(a+b)c$? Apr 12 '12 at 2:03
• Yes, parentheses are allowed. Apr 12 '12 at 2:41
• For what it's worth, the sequence without the positivity requirement is oeis.org/A140606. Apr 12 '12 at 3:39

I think that I have worked out a solution for my problem. An expression with $k \ge 2$ variables is either a sum of two or more products, or it is a product of two or more sums. I'm using the word "sum" broadly to include addition and subtraction, and "product" to include multiplication and division.

By iterating through all partitions of $k$, I obtained recurrences for the number of sum representations and the number of product representations. These recurrences allowed me to count the number of arithmetical combinations of 50 numbers in under three minutes.

My Python script is here: http://codepad.org/p7SJU7gg