The number of permutations of 1..n with k left to right maxima is given by the Stirling Numbers of the first kind. See, for example: http://blog.tanyakhovanova.com/?p=451 . Since we have an explicit generating function for them (see Wikipedia, for example), we can easily calculate any moment of their distribution. Victor On Tue, Apr 16, 2013 at 12:13 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Here's a cute and useful fact.
Let S be a set of N numbers. Permute them into random order. Scan thru the elements in that order. Each time you encounter a new record max, ring a bell. So for example, if S={7*,8*,5,3,4,9*} you would ring the bell 3 times at the *s.
EASY CLAIM: expected number of times the bell rings, equals HarmonicNumber(N) = 1+1/2+1/3+...+1/N.
HARDER QUESTIONS, which I have not looked at: What about the variance? What about tail bounds? Can you write a formula for the whole probability distribution for the number of bell-rings: Prob(R) = xxx?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun