3
$\begingroup$

Given 's' students in a room and 'd' days in the calendar year, what is the probability 'P' that there will be 'k' "birthday days"?

i.e., 'k = 1' means that everybody's birthday falls on the same day, 'k = 5' means that exactly 5 days of the year coincide with the birthday of at least one student, and 'k = s' means that everyone's birthday is unique.

Assume d ≥ s. 'k' will range from 1 to 's', and ∑P from k = 1 to k = s will be 1 (in other words, P(k) is a probability mass function).

What I Know So Far:

• The total number of ways for the students to have birthdays is d^s.

• P(1) = d/d^(s) (because there are 'd' days on which all students could all share the exact same birthday).

• P(s) = d!/(d^(s)(d-s)!) (because this is compliment of the solution to the standard birthday problem)

Any help/resources that get me closer to a formula for P(k) are greatly appreciated. Thanks!

$\endgroup$
2
$\begingroup$

Outline: Under the usual assumptions, there are $d^s$ equally likely ways for the students to be assigned birthdays.

We now need to count the "favourables," the number of ways students can be assigned $k$ birthdays. The $k$ days on which Happy Birthday will be sung can be chosen in $\binom{d}{k}$ ways.

Now we multiply $\binom{d}{k}$ by the number of ways students can be assigned birthdays on some specific $k$ days, so that none of the $k$ days is missed. To calculate this, look at the Wikipedia article on Stirling numbers of the Second Kind. We need to count the number of onto functions from an $s$-element set to a $k$-element set. There are also many questions/answers on MSE about the number of onto functions.

$\endgroup$
4
  • $\begingroup$ Thanks so much for tip on Stirling numbers of the second kind, that was exactly what I needed! The s^d vs. d^s mixup was just a typo on my part, but I appreciate the correction there too. $\endgroup$ Jul 22 '16 at 19:56
  • $\begingroup$ You are welcome, I removed the remark after you edited. $\endgroup$ Jul 22 '16 at 20:00
  • $\begingroup$ Final comment: I also realized that, because the Stirling number of the second kind counts the number of ways to partition a set of 'n' labelled objects into 'k' nonempty unlabelled subsets, the Stirling number must be multiplied by 'k!' to account for all the "orderings" of the day subsets. The final formula works out to be P(k) = (nchoosek(d,k)S(s,k)k!)/(d^s). Thanks again! $\endgroup$ Jul 22 '16 at 20:05
  • $\begingroup$ Yes, that;s right. Another way to think of it is that the usual Inclusion/Exclusion expression for the Stirling numbers involves dividing a count by $k!$. For your application, you don't want to divide, so to undo the division built into the computation of Stirling numbers we must multiply $S(s,k)$ by $k!$. $\endgroup$ Jul 22 '16 at 20:13

Your Answer

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

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