Averaging problem

[David Wilson]

So, regardless of how we define ab (in particular, if we define ab = 
(a+b)/2, as in the problem), an expression with  n operands can be 
parenthesized in C(n-1) ways, with each parenthesization having the same 
value regardless of order of parenthetic evaluation, so that an expression 
involving n operands has at most C(n-1) possible distinct values.

On the other hand, certain choices of operations and operands can lead to 
fewer than C(n-1) expression values. For example, if ab is reflexive (as is 
ab = (a+b)/2), then choosing equal operands equal yields the same value 
regardless of parenthesization, falling short of the potential C(n-1) 
distinct values for n >= 3.  Worse yet, if ab is associative, any choice of 
operands yields a value independent of parenthesization.

I can imagine situations in which things are not quite so drastic. For 
example, if ab satisfied a(b(cd)) = ((ab)c)d but were not associative 
(supposing this to be possible), then for sufficient n, the maximum number 
of expression values would exceed 1 but fall short of the potential C(n-1).

The upshot is, for ab = (a+b)/2, I see at most C(n-1) best-case distinct 
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, or 
new interpretation of an existing sequence, out of this line of inquiry.

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

----- Original Message ----- 
From: "Maximilian Hasler" <maximilian.hasler at gmail.com>
To: "Brendan McKay" <bdm at cs.anu.edu.au>
Cc: "David Wilson" <davidwwilson at comcast.net>; "Sequence Fans" 
<seqfan at ext.jussieu.fr>
Sent: Monday, November 26, 2007 8:23 AM
Subject: Re: Averaging problem


>I agree that it should coincide with
>
> A000108  Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
> (2n)!/(n!(n+1)!). Also called Segner numbers.
>
> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
> 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190,
> 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324
> (list; graph; listen)
>
> COMMENT
> Number of ways to insert n pairs of parentheses in a word of n+1
> letters. E.g. for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d),
> ((a(bc))d), (a((bc)d)), (a(b(cd))).
>
>
> I think the given comment explains the equivalence with the averaging 
> process.
> Maximilian
>
>
> On Nov 26, 2007 6:01 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:
>> I guess it is the number of binary trees with n leaves and all
>> non-leaf nodes having two children, also the number of ways to
>> fully bracket a sequence of n items;  i.e., a Catalan number.
>>
>> If the leaves of the tree are associated with values x_1,...,x_n,
>> then the final value is the sum of 2^(-a_i)*x_1, where a_i is the
>> depth of the i-th leaf (the root has depth 0). If the x_i's are
>> linearly independent over the rationals, each tree gives a distinct
>> final value.
>>
>> Brendan.
>>
>> * David Wilson <davidwwilson at comcast.net> [071126 20:08]:
>>
>> > Suppose we start with a sequence S of n >= 1 real values. At each turn, 
>> > we
>> > select two adjacent values at random and replace them with their 
>> > average.
>> > After n-1 turns, S is reduced to a single number. This number will 
>> > depend
>> > the values in S and on which pairs that chosen to average.
>> >
>> > For a given S with n elements, there are (n-1)! ways to apply the 
>> > averages,
>> > hence we might expect (n-1)! possible final values for a fortuitously
>> > chosen S.  It is easy to verify that a sequence S of 1 elements results 
>> > in
>> > 0! = 1 possible value (the value of its element) after 0 averages.
>> > Similarly, a sequence S of 2 elements results in 1! = 1 possible value 
>> > (the
>> > average of its elements) after 1 average. For n = 3, the sequence S = 
>> > (1,
>> > 5, 9) gives the 2! = 2 possible final values 4 or 6 depending on which
>> > adjacent pair we choose to average first.
>> >
>> > At n = 4, however, there are fewer than 3! = 6 possible values. 
>> > Starting
>> > with a sequence of 4 elements, if we average the first pair, then the 
>> > last
>> > pair, then the only pair, we end up with the same value as when we 
>> > average
>> > the last pair, then the first pair, then the only pair. This means 
>> > there
>> > are at most 5 distinct final values (in fact, there are sequences of 4
>> > elements with 5 final values, e.g, (8, 16, 32, 64), which has final 
>> > values
>> > 20, 26, 30, 40, and 43.
>> >
>> > The question is, for a sequence of n elements, what is the largest 
>> > possible
>> > number final values? The sequence begins 1, 1, 2, 5, ... for n = 1, 2, 
>> > 3,
>> > 4, ...
>> >
>>
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.5.503 / Virus Database: 269.16.7/1152 - Release Date: 
> 11/26/2007 10:50 AM
>