David Lyness's Blog

If you have \(n\) instances of some digit \(d\) between \(0\) and \(9\), thare multiple ways of writing these digits using some ordering of parentheses and a binary operator between them.

Consider the case of four \(2\)s. In this case, \(n=4\) and \(d=2\). Then there are five different ways parentheses could be inserted into the expression using the binary operator \(\cdot\) in all three positions:

\(\left ( \left (2 \cdot 2 \right ) \cdot \left (2 \cdot 2 \right )\right )\)

\(\left ( \left ( \left ( 2 \cdot 2 \right ) \cdot 2 \right ) \cdot 2 \right )\)

\(\left ( \left ( 2 \cdot \left (2 \cdot 2 \right ) \right ) \cdot 2 \right )\)

\(\left (2 \cdot \left ( \left ( 2 \cdot 2 \right ) \cdot 2 \right ) \right )\)

\(\left (2 \cdot \left (2 \cdot \left ( 2 \cdot 2 \right ) \right ) \right )\)

Since there is no requirement that \(\cdot\) is associative, all five of these expressions could evaluate to different values.

To procedurally generate all possible permutations of parentheses given \(n\) digits, we can define a function as follows:

def all_parentheses(expr):
    """
    Generates all possible permutations of parentheses for an expression.
    @param str expr: the source expression without parentheses
    @rtype: str
    """
    if len(expr) == 1:
        yield expr
    else:
        for i in range(1, len(expr), 2):
            for left_expr in all_parentheses(expr[:i]):
                for right_expr in all_parentheses(expr[i+1:]):
                    yield f'({left_expr}{expr[i]}{right_expr})'

If we relax the requirement that all binary operators in the expression be the same, there are \(4^{3} \times 5=320\) unique expressions if we restrict ourselves to the standard arithmetic operators of addition, subtraction, multiplication and division. Here are a few examples from the \(320\) possible combinations:

\(\left ( \left (2 + 2 \right ) -\left (2/2 \right )\right )=3\)

\(\left ( \left (2 + 2 \right ) /\left (2-2 \right )\right )\) is undefined due to division by zero

\(\left ( \left ( 2 \times \left ( 2 \times 2 \right ) \right ) +2\right )=10\)

I’m calling the first and third expressions defined, and the second not defined (since the result of evaluating the expression is undefined). Given the above restrictions on parentheses and binary operators, the only way an expression cannot be defined is for division by zero to occur.

Questions

We could ask the following questions in terms of \(n\) and \(d\):

1. What’s the maximum value an expression can evaluate to?
2. What’s the minimum value an expression can evaluate to?
3. What’s the smallest (absolute) value an expression can evaluate to?
4. How many expressions exist?
5. How many defined expressions exist?

Maximum value

Continued multiplication grows fastest as \(n\) grows. So, a likely candidate for the maximum value is \[\underbrace{d\times d \times \dots \times d}_{n\text{ times}}=d^{n}.\] Spot-checking the data confirms this too — for example, when \(d=7\):

The only exception is when \(d=1\), because \(1\times 1 < 1 + 1\). In this case, the 1’s can be partitioned into groups of three, and then multiplied together. For example: \[\left ( \left ( 1+\left ( 1+1 \right ) \right ) \times \left ( 1+\left ( 1+1 \right ) \right )\right )=9.\]

The closed form for the maximum expression value when \(d=1\) is \[\text{maximum}(n)=\begin{cases} 1 &\mbox{if } n = 1 \\ \frac{3^{\left \lfloor \frac{n}{3} \right \rfloor}}{1-\frac{n\mod 3}{4}} & \mbox{if }n>1. \end{cases}\]

Alternatively, a more readable recurrence relation is \[\text{maximum}(n)=\begin{cases} n&\mbox{if } n < 4 \\ 3\times\text{maximum}(n-3) &\mbox{if }n\geq 4. \end{cases}\]

Minimum value

The minimum value (or “most negative”) is closely related to the maximum value. If the maximum value is \(M\), then the minimum value can be no smaller than \(-M\), as otherwise we would then have a symmetric method to achieve a maximum value greater than \(M\). In fact, the minimum value is achieved when we calculate the maximum value for \(n-1\), and subtract this from the remaining \(d\): \[d-\underbrace{d\times d \times \dots \times d}_{n-1\text{ times}}=d-d^{n-1}.\] And when \(d=7\) as before:

Smallest value

The smallest value differs from the minimum value as it is the value closest to zero. It turns out that for \(n>1\) we can always find an expression equal to zero for a given \(d\): \[\underbrace{d\times d \times \dots \times d}_{n-2\text{ times}}\times\left(d-d \right )=d^{n-2}\times 0=0.\] So, maybe it’s more interesting to look at the smallest non-zero value.

Smallest non-zero value

The smallest non-zero value can be calculated in a similar way to the minimum value. Whereas with the minimum we wanted the most negative expression — and therefore subtracted \(d^{n-1}\) from \(d\) — for the smallest value, we want to divide \(d\) by \(d^{n-1}\): \[\frac{d}{\underbrace{d\times d \times \dots \times d}_{n-1\text{ times}}}=d^{2-n}.\]

Total expressions

Ignoring distinct binary operations for a moment, the number of ways to insert parentheses into an expression with \(n\) digits is as follows.

These are the Catalan numbers. Their closed form is \(C(0)=1\), and \[C(n)=\frac{1}{n+1}\sum_{i=0}^{n}\binom{n}{i}^{2}.\] Since the \(n\) in \(C(n)\) refers to the number of pairs of parentheses rather than the number of digits in this problem, the number of expressions for \(n\) digits is equal to \(C(n-1)\).

However, this doesn’t provide every single expression for a given \(n\) — we need to take the choices of binary operator into account too. We have \(n-1\) positions into which to place binary operators, and for each position there are four binary operators to choose from. The total number of expressions for a given \(n\) is therefore \[4^{n-1}\times C(n-1).\]

Total defined expressions

Not all expressions are defined — some include a division by zero operation which results in the expression’s value being undefined.

The following table shows the total number of expressions overall for each \(n\), and the total number of defined expressions for each \(d\) — they differ in an interesting way!

Reading from left to right across a row of the table (i.e. as \(d\) increases for the same \(n\)), the number of defined expression stabilises. For example, for \(n=5\), the monotonically-increasing sequence is \[1134,3275,3337,3345,3345,\dots,3345.\]

Each value highlighted in the table above is one which is strictly less than its stabilised counterpart (i.e. \(1134\), \(3275\) and \(3337\) are highlighted above because they are all less than \(3345\)). This sequence is bounded above by the total number of expressions (calculated previously as \(4^{n-1}\times C(n-1)\)), but a more precise derivation is still to be determined. One good thing has come out of this though — a new sequence has been approved and added to the On-Line Encyclopedia of Integer Sequences (OEIS) — check out A243312.

Summary