3
$\begingroup$

Say we have $n$ people and $k$ days. What is the probability that NO two of the $n$ people are born on the same day?

This is of course assuming that $n \leq k$ (otherwise the answer is $0$ by the pigeonhole principle!). I said the answer was: $k \choose n$$\cdot n! \cdot \frac{1}{k^n}$ because in order for this to happen, n distinct birthdays must be chosen, they can be arranged in any way amongst the $n$ people, and there are $k^n$ total arrangements. Is this correct?

$\endgroup$
  • 3
    $\begingroup$ Your answer appears correct to me. A good way to make sure of this would be to check for small values of $n$ and $k$ that you could count all the possible outcomes by hand and solve the probability that way and see if your formula simplifies to the same answer. $\endgroup$ – WaveX Oct 15 '18 at 18:27
  • 2
    $\begingroup$ This is the well-known "birthday problem". Your answer appears to be correct. Also if $n > k$ your formula still holds, because then ${k \choose n}$ is zero by definition. $\endgroup$ – Michael Lugo Oct 15 '18 at 19:38
  • $\begingroup$ Thank you both! Didn't realize it's a common problem. $\endgroup$ – 0k33 Oct 15 '18 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.