Averaging problem

[Maximilian Hasler]

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