Averaging problem

franktaw at netscape.net franktaw at netscape.net
Tue Nov 27 10:14:41 CET 2007

Take the n values to be distinct powers of 2^n.  The weight of each
value in the final result is always a power of 2 between 2^0 and 
(2^0 occurs only for n=1, but that doesn't affect the argument.)
Looking at the binary expansion of the final average, we can tell 
what weight was assigned to each number.

 From the weights, it is easy to determine the exact parenthesization
tree.  The final operation occurs exactly where the running sum of the
weights is 1/2.  If there is more than number on one side of the
operation, the last operation on that side occurs where the sum (on
that side) is 1/4, etc.


I don't think that all possible values can be obtained.  For n > 1, any
given number can be given any power of 2 weight between 2^-1
and 2^-(n-1).  This means that operands all the same except for one
different value will produce n-1 distinct values.  While 1 value is of
course always obtainable (just take all operands equal), I don't see
any way to get strictly between 1 and n-1 distinct values.  I don't
know if there are other unobtainable values between n-1 and C(n-1),
but I expect there are.

Franklin T. Adams-Watters

-----Original Message-----
From: David Wilson <davidwwilson at comcast.net>


The upshot is, for ab = (a+b)/2, I see at most C(n-1) best-case 
values of an n-operand expression, but I don't immediately see exactly
C(n-1) best-case distinct values. I stand ready to be amazed, though.


Even if we do show that ab = (a+b)/2 leads to C(n-1) best-case distinct
values of n operands, I am bound and determined to get a new sequence, 
new interpretation of an existing sequence, out of this line of 

We agree that for judiciously defined ab, an n-operand expression can 
most C(n-1) distinct values, one for each parenthesization. However, I 
skeptical that an n-operand expression can take on any number of 
values between 1 and C(n-1) inclusive. Is there, for example, an 
expression with exactly 7 values? How many possible numbers of distinct
values can an n-operand expression take on by varying parentheses?

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

More information about the SeqFan mailing list