> 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
Bring (1/n!) out of the sum and consider sum_{m=0 to n} m * D(n,m).
A particular term "m * D(n,m)" is just the total number of elements in
the right place among the set of permutations that have exactly m
elements in the right place.
The sum over all m of "m * D(n,m)" is then the total number of
elements in the right place over all permutations.
But this value is exactly N!, since for slot i, there are exactly
(N-1)! permutations that have the value i in slot i.
The above quantity then becomes (N!) / (N!) or 1.
Greg Johnson
--
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.
