How many solutions can an Integermania problem have?

Theorem:  In an Integermania problem with n values and k available binary operations, where each value is used exactly once, and values are combined by using only the available binary operations, there are at most k to the power n minus one, times the factorial of two n minus two, divided by the factorial of n minus one positive integers which can be created.

Outline of Proof:  Let a set of n values mi be fixed, and let pj denote the k available binary operations.  A solution s can be uniquely described by the sequence of operations p used on the n values to obtain s, and will take the form m1p1m2p2...pn–1mn, with parentheses to determine the order of operations.  Since the n values are assumed to be distinct and not repeated, there are n! ways to order the values in the above solution form.   The operations can be repeated, and are chosen from a set of k possible operations.  There are kn–1 ways to select those operations.  The number of ways to insert sets of parentheses is C(n–1), a term of the sequence of Catalan numbers given by  C of n equals one over n plus one, times the binomial coefficient two n choose n.  Multiplying these three factors gives the result.  See proof for more details.

A Worst Case Example:  Define the set of values a,b elements of {1,2,3,4}, and the four operations:
a operation sub k b equals k times 10 to the power 2 plus the log base 10 of a rounded down plus the log base 10 of b rounded down, plus a times 10 to the power 1 plus the log base 10 of b rounded down, plus b,
for k element of {5,6,7,8}.  It can be shown that the result of each of these four operations is equivalent to writing the juxtaposed result kab, both of which are equivalent to the original operation written in prefix notation.  In other words, each result retains all of the information about the operations, value, and order of operations used to produce it, and therefore any combination of the operations is one-to-one.  There are 7680 ways in which all four values can be used exactly once each, using three of the four available binary operations, as stated by the theorem.  Each of those ways gives a different 15-digit positive integer solution.

Comments:  The worst case example provides evidence that the formula given by the theorem is the best possible bound on the number of solutions without additional information about the values or the operations.  But for a particular Integermania problem, the number of possible positive integer solutions may be much smaller, due to repeated values in the set of values, operations which are commutative, solutions which are not positive integers, or solutions which can be produced in more than one way.

Back to Theorems and Conjectures.