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.

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.  The number of solutions will be found by the product of three quantities:

  1. number of ways to arrange the n values
  2. number of ways to choose the (n – 1) operations
  3. number of ways to insert parentheses

Arrangements of the n values are permutations of the original set.  Since the n values are assumed to be distinct and not repeated, and all n values are to be arranged, there are n! ways to order the values in the above solution form.

Choices for the (n – 1) operations are made from a set of k possible operations, and the operations can be repeated.  This is an application of the basic multiplication principle of enumeration, so there are kn–1 ways to select those operations.

We claim that the number of ways to insert sets of parentheses into a solution of n values 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. Establishing this claim will take a little more effort.

Let Pn–1 be the number of ways in which a solution of the form m1p1m2p2...pn–1mn can be correctly parenthesized.  (Note that the subscript of P is the number of operations in the solution.)  Each solution has an operation which occurs last, according to the order of operations identified by the parentheses. Assume that pq is that operation, where q is an element of {1,2,3,...,n–1}. The two quantities which that operation joined are m1p1m2p2...pq–1mq (having q–1 operations) and mq+1pq+1mq+2pq+2...pn–1mn (having n–q–1 operations). For solutions of n values where the last operation occurs in the qth position, then the number of solutions Pn–1 is equal to the product of the number of solutions of q values Pq–1 with the number of solutions of n–q values Pn–q–1. Considering all possible last positions q, we find the recursive relation for the number of parenthesizings is
P sub n minus one equals the sum from q equals one to n minus one, of P sub q minus one, times P sub n minus q minus one,
and P0 = 1. To make it easier to work with this result, we change the indices and subscripts to obtain the equivalent relation
P sub n plus one equals the sum from q equals zero to n, of P sub q times P sub n minus q.

To determine an explicit formula for Pn, we shall use the sequence as coefficients in the power series
P of x equals the sum from n equals zero to infinity of P sub n x to the power n, which equals one plus the sum from n equals zero to infinity of P sub n plus one times x to the power n plus one.
Substituting the recursion relation into this definition, we obtain
P of x equals one plus the sum from n equals zero to infinity of the sum from q equals zero to n of P sub q times P sub n minus q times x to the power n plus one.
Reversing the order of summation gives
P of x equals one plus the sum from q equals zero to infinity of the sum from n equals q to infinity of P sub q times P sub n minus q times x to the power n plus one.
Now we can factor out common factors from the second summation to give
P of x equals one plus the sum from q equals zero to infinity of P sub q times x to the power q plus one, times the sum from n equals q to infinity of P sub n minus q times x to the power n minus q,
which simplifies to
P of x equals one plus the sum from q equals zero to infinity of P sub q x to the power q plus one times P of x, which equals one plus x times P of x times the sum from q equals zero to infinity of P sub q x to the power q, which equals one plus x times the square of P of x.

Solving this equation for P(x) using the quadratic formula, we obtain
P of x equals one minus the square root of one minus four x, all divided by two x.
(We discarded the other solution, since the function is supposed to have a power series representation centered at x = 0 that would not be provided by using the positive sign.)

Now that we know a formula for P(x), we can generate the Taylor series expansion for it, and equate its coefficients with Pn. Taylor's Formula on a simpler function gives:
square root of one plus x equals one plus one-half x, minus one over 2 squared times x squared over 2 factorial, plus 1 times 3 over 2 cubed times x cubed over 3 factorial, minus et cetera, which equals one plus the sum from k equals one to infinity of negative one to the power k plus one, times two k minus 2 factorial, times x to the power k, all divided by 2 to the power k times 2 to the power k minus one, times k minus one factorial, times k factorial
Substituting (–4x) in place of the variable x, we obtain
square root of one minus four x equals one minus the sum from k equals one to infinity of two, times two k minus two factorial, times x to the power k, all divided by k factorial times k minus one factorial.
Therefore
P of x equals one over two x, times the sum from k equals one to infinity of two, times two k minus two factorial, times x to the power k, divided by k factorial times k minus one factorial, which equals the sum from k equals one to infinity of two k minus two factorial, times x to the power k minus one, all divided by k factorial times k minus one factorial.
Reindexing, we obtain
P of x equals the sum from k equals zero to infinity of two k factorial times x to the power k, all divided by k factorial times k plus one factorial, which equals the sum from k equals zero to infinity of the binomial coefficient two k choose k, times x to the power k, divided by k plus one.
Equating the terms of this sequence with the coefficients from our original definition of P(x), we find
P sub n equals the binomial coefficient two n choose n, divided by n plus one
which is the definition of the Catalan sequence.

Referring back to our original definition of Pn, we note that the subscript identifies the number of operations used. The number of values is actually one more than the number of operations, so Pn–1 is the number of parenthesizings for a set of n values. Therefore, the number of possible solutions can not exceed
n factorial times k to the power n minus one times P sub n minus one equals n factorial times k to the power n minus one times the binomial coefficient two n minus 2 choose n minus one, divided by n, which equals k to the power n minus one times two n minus two factorial, divided by n minus one factorial
This completes the proof of the theorem.

Back to discussion and worst case example.