Hello,
here is an slightly alternative argument to see why on average a
permutation
brings one element into its correct position:
Hitting the table with n elements not pinned down is equivalent
to drawing a random permutation of length n (and it does not matter
in which order the non-pinned down elements were before the hit).
Let's call D(n,m) the number of permutations of n elements which have
m elements in the good position (i.e. number i is on the ith place).
The probability of getting m hits in the right place is therefore
D(n,m) / n! .
To get the expected (i.e. average) number of hits in the right place,
one has to sum over m, weighted by the probability to get exactly
m hits in the right place:
sum_{m=0 to n} k * D(n,m) / n!
Now D(n,m) is also known as Rencontres number (see e.g.
http://en.wikipedia.org/wiki/Rencontres_numbers) and when one
looks at one of the references in this article (http://oeis.org/
A008290)
one sees in the 'formula' section that the above expression
is indeed 1 (no proof is given there however).
Andre
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
