Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having trouble solving exercise 3.4 from E. T. Jaynes' Probability Theory: The Logic of Science.

There are M urns numbered 1 to M, and M balls, also numbered one to M, which are thrown into them, one in each urn. If the numbers of a ball and its urn are the same, we have a match. Show that the probability for at least one match is: $$h = ∑_{k=1}^M{ \frac{(-1)^{(k+1)}}{k!} }$$

How do I solve it?

share|cite|improve this question
The more information you give about what you do understand about this problem, or about how far you have got by yourself, the more likely you are to get a useful answer. – Chris Godsil Feb 3 '13 at 3:58
up vote 0 down vote accepted

The problem of finding the number of ways to do it with no match is the classical problem of counting derangements. For the probability of no match one divides by $M!$.

The Wikipedia article linked to gives a good overview, and includes a proof.

The problem has also been asked and answered repeatedly on MSE.

share|cite|improve this answer
Thank you, and I'm very sorry about repeating the question! I wasn't aware of the name "derangement" or the concept. – Pedro Carvalho Feb 3 '13 at 3:56
@PedroCarvalho: No problem! A vast majority of the problems on MSE yield to known results. – André Nicolas Feb 3 '13 at 6:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.