puzzle family: values of parenthesized expressions

[Marc LeBrun]

In general, Catalan(N) unique values cannot be achieved.

If the expression has 2 + operators, we can look at the 
parenthesizations that group everything else first, giving us an 
expression of the form a + b + c.  E.g., starting with 2 * 3 - 4 + 8 + 
7 * 2, we can group ((2*3)-4) + 8 + (7*2), giving a = 2 * 3 - 4, b = 8, 
c = (7*2).  Now, grouping this as either (a + b) + c or a + (b + c) 
will produce the same result.

The same thing results when there are 2 * operators.

If there are 3 - operators, we can group to get a - b - c - d, and now 
(a - (b - c)) - d = a - (b - (c - d)).

This means that Catalan(N) is not obtainable for N > 4.  But Catalan(4) 
is also not obtainable: the only possibility is to have one +, one *, 
and two - operators.  But if the + precedes either -, we can group as a 
+ b - c, and (a + b) - c = a + (b - c).  So the + must follow both - 
operators - and now we can group as a - b - c + d, and (a - (b - c)) + 
d = a - (b - (c + d)).

Catalan(3) is obtainable: 1 - 2 * 3 + 4 gives the values {1, -1, -7, 
-9, -13}.  Also, 1 - 2 * 3 - 4 gives values {1, -1, 3, -7, -9} using 
just {- *}; however, {+ *} can produce Catalan(N) only for N <= 2.

There are some sequences in the OEIS relating to the number of possible 
values you get when you just use exponentiation, with all numbers the 
same.  See, e.g., A082499, which has links to some others.

Franklin T. Adams-Watters


-----Original Message-----
From: mlb at well.com

... find the number of unique 
values of an infix expression (like say 1+2-3*4) parenthesized in all 
possible ways 
... The operators were restricted to {+ - *}, the operands to positive 
integers. 
 
... is there a method for constructing such expressions such 
that over parenthesization they give the maximum possible Catalan(N) 
unique values? 
 
What is the maximum achievable if the operators are restricted to {+ *} 
or {- *}? 


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.