We use MathJax
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 $\dfrac{k^{n-1} (2n-2)!}{(n-1)!}$ positive integers which can be created.
Proof: Let a set of $n$ values $m_i$ be fixed, and let $p_j$ 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 $m_1 p_1 m_2 p_2 \cdots p_{n-1} m_n$, with parentheses to determine the order of operations. The number of solutions will be found by the product of three quantities:
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 $k^{n-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(n) = \frac{1}{n+1} \binom{2n}{n}$. Establishing this claim will take a little more effort.
Let $P_{n-1}$ be the number of ways in which a solution of the form $m_1 p_1 m_2 p_2 \cdots p_{n-1} m_n$ 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 $p_q$ is that operation, where $q \in \{1,2,3, ..., n-1 \}$. The two quantities which that operation joined are $m_1 p_1 m_2 p_2 \cdots p_{q-1} m_q$ (having $q-1$ operations) and $m_{q+1} p_{q+1} m_{q+2} p_{q+2} \cdots p_{n-1} m_n$ (having $n - q - 1$ operations). For solutions of $n$ values where the last operation occurs in the $q$th position, then the number of solutions $P_{n-1}$ is equal to the product of the number of solutions of $q$ values $P_{q-1}$ with the number of solutions of $n-q$ values $P_{n-q-1}$. Considering all possible last positions $q$, we find the recursive relation for the number of parenthesizings is
\begin{equation} P_{n-1} = \sum\limits_{q=1}^{n-1} P_{q-1} P_{n-q-1} \end{equation}with $P_0 = 1$. To make it easier to work with this result, we change the indices and subscripts to obtain the equivalent relation
\begin{equation} P_{n+1} = \sum\limits_{q=0}^n P_q P_{n-q} \end{equation}To determine an explicit formula for $P_n$, we shall use the sequence as coefficients in the power series
\begin{equation} P(x) = \sum\limits_{n=0}^\infty P_n x^n = 1 + \sum\limits_{n=0}^\infty P_{n+1} x^{n+1} \end{equation}Substituting the recursion relation into this definition, we obtain
\begin{equation} P(x) = 1 + \sum\limits_{n=0}^\infty \left( \sum\limits_{q=0}^n P_q P_{n-q} x^{n+1} \right) \end{equation}Reversing the order of summation gives
\begin{equation} P(x) = 1 + \sum\limits_{q=0}^\infty \left( \sum\limits_{n=q}^\infty P_q P_{n-q} x^{n+1} \right) \end{equation}Now we can factor out common factors from the second summation to give
\begin{equation} P(x) = 1 + \sum\limits_{q=0}^\infty \left( P_q x^{q+1} \sum\limits_{n=q}^\infty P_{n-q} x^{n-q} \right) \end{equation}which simplifies to
\begin{align} P(x) &= 1 + \sum\limits_{q=0}^\infty P_q x^{q+1} P(x) \\ &= 1 + x P(x) \sum\limits_{q=0}^\infty P_q x^q \\ &= 1 + x (P(x))^2 \end{align}Solving this equation for $P(x)$ using the quadratic formula, we obtain
\begin{equation} P(x) = \dfrac{1 - \sqrt{1 - 4x}}{2x} \end{equation}(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 $P_n$. Taylor's Formula on a simpler function gives:
\begin{align} \sqrt{1+x} &= 1 + \dfrac12 x - \dfrac{1}{2^2} \dfrac{x^2}{2!} + \dfrac{1 \cdot 3}{2^3} \dfrac{x^3}{3!} - \cdots \\ &= 1 + \sum\limits_{k=1}^\infty \dfrac{(-1)^{k+1} (2k-2)!}{2^k 2^{k-1} (k-1)!} \dfrac{x^k}{k!} \end{align}Substituting $(-4x)$ in place of the variable $x$, we obtain
\begin{equation} \sqrt{1-4x} = 1 - \sum\limits_{k=1}^\infty \dfrac{2(2k-2)!}{k! (k-1)!} x^k \end{equation}Therefore
\begin{align} P(x) &= \dfrac{1}{2x} \sum\limits_{k=1}^\infty \dfrac{2(2k-2)!}{k! (k-1)!} x^k \\ &= \sum\limits_{k=1}^\infty \dfrac{(2k-2)!}{k! (k-1)!} x^{k-1} \end{align}Reindexing, we obtain
\begin{align} P(x) &= \sum\limits_{k=0}^\infty \dfrac{(2k)!}{k! (k+1)!} x^k \\ &= \sum\limits_{k=0}^\infty \dfrac{1}{k+1} \binom{2k}{k} x^k \end{align}Equating the terms of this sequence with the coefficients from our original definition of $P(x)$, we find
\begin{equation} P_n = \dfrac{1}{n+1} \binom{2n}{n} \end{equation}which is the definition of the Catalan sequence.
Referring back to our original definition of $P_n$, 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 $P_{n-1}$ is the number of parenthesizings for a set of $n$ values. Therefore, the number of possible solutions can not exceed
\begin{equation} n! k^{n-1} P_{n-1} = \dfrac{n! k^{n-1}}{n} \binom{2n-2}{n-1} = \dfrac{k^{n-1} (2n-2)!}{(n-1)!} \end{equation}This completes the proof of the theorem.
Back to discussion and worst case example.