Averaging problem

[Brendan McKay]

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