puzzle family: values of parenthesized expressions

[Antti Karttunen]

(This doesn't reach math-fun at mailman.xmission.com because I'm not a member.)

franktaw at netscape.net wrote:

> In general, Catalan(N) unique values cannot be achieved.
>
Depends on the operator. It does not need to be commutative.
Let's define (x @ y) = 1+ ( ( x + (x+y)^2 + 3y) / 2 )

Then (0 @ 0) = 1

(0 @ (0 @ 0)) = 3
((0 @ 0) @ 0) = 2

(0 @ (0 @ (0 @ 0))) = 10
(0 @ ((0 @ 0) @ 0)) = 6
((0 @ 0) @ (0 @ 0)) = 5
((0 @ (0 @ 0)) @ 0) = 7
(((0 @ 0) @ 0) @ 0) = 4

etc.
See http://www.research.att.com/~njas/sequences/A071653
(The graph looks nice, like fractal clouds of smoke from an old steam 
engine.
I have to compute a b-file for this.)

-- Antti

> 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.
>
>