Wikipedia:Reference desk/Science/Birthday probability question

This came up at my conscientious objector place. We know that if there is a group of over 365 people, at least two people will have the same birthday. But if we pose the question "backwards", i.e. how large a group of people has to be so that every day of the year is a birthday of someone? The correct answer, of course, is "infinite", as there is nothing preventing, for example, everyone from being born on the same day.

But given the number of people, what is the probability of every day in the year being someone's birthday? For 1 to 364 people, it is 0, i.e. such a thing is impossible. For exactly 365 people, it is 1/(365!), i.e. 1 divided by the factorial of 365. But what is the probability for larger groups? (For simplicity, we ignore leap years.) — JIP | Talk 16:38, 27 October 2005 (UTC)[reply]

Your math basis is incorrect. The probability that 365 people have distinct birthdays is 365!/365^365. (1/365! is the probability that you take 365 people with distinct birthdays and, picking them one at a time, correctly pick them in birthday order). Let's work with smaller numbers: assume a 3-sided coin (it's more interesting than a two-sided, but the numbers are small). Leaving order intact, there are 3*3*3 or 27 combinations of flips with results a, b, and c. Of these, only 3! (abc, acb, bac, bca, cab, cba) have all 3 results, for 3!/3^3 probability. For a fourth flip, there are 3^4 or 81 combinations. Every 3-ple satisfying 3 flips will work with any fourth value (that's 6*3), and every 3-ple with 2 distinct values will satisfy for one particular fourth value (that's 18*1), a grand total of 36 working combinations. For a fifth, all the working 4-tuples with any (36*3), plus all the failed 2-item 3-tuples with the needed third value (18*2*1), plus the 1-item 3-tuples with a distinct fourth value plus the needed fifth (3*2*1), a grand total of 150/243. If somebody else can come along and make this into a series... you're better with symbols than me. — Lomn | Talk / RfC 17:56, 27 October 2005 (UTC)[reply]

I've got a recursive solution, but I'm not sure how (or if it's possible) to get a closed formula. Let ${\displaystyle f(M,N)}$ be the number of ways of distributing M distinct balls among N distinct bins, with each bin containing at least one ball; and let ${\displaystyle g(M,N)}$ be the number of ways of distributing M distinct balls among N distinct bins, possibly having one or more bins empty. (Throughout this, consider "balls" and "bins" to always refer to distinct balls, such as individually numbered balls, and distinct bins, so I don't have to keep specifying "distinct.")

Thus, the probability you are looking for is ${\displaystyle {\frac {f(M,N)}{g(M,N)}}}$. If you want to know the probability of having every day represented in a group of 1000 people, you are looking for ${\displaystyle {\frac {f(1000,365)}{g(1000,365)}}}$.

g is easy: ${\displaystyle g(M,N)=N^{M}}$.

f is the difficult one. One way to compute the number of ways of distributing M balls among N bins, with at least one ball in each bin, then subtracting the number of ways of distributing M balls among N bins, with at least one bin being empty.

Let's consider 7 balls placed into 4 bins. The number of ways of distributing them, with no restriction, is ${\displaystyle g(7,4)=4^{7}=16384}$. Now, we need to subtract the number of those ways which leave one or more bins empty. Let's consider the separate cases of exactly one bin empty, exactly two bins empty, and exactly three bins empty.

The number of ways of placing 7 balls into 4 bins, leaving exactly 1 specific bin empty, is ${\displaystyle f(7,3)}$. So the number of ways to place 7 balls into 4 bins, leaving exactly 1 (but not any specific bin) empty, is ${\displaystyle 4\cdot f(7,3)}$.

Similarly, to place 7 balls into 4 bins, leaving 2 specifc bins (and no others) empty, is ${\displaystyle f(7,2)}$. Since there are 6 different ways to choose 2 bins to remain empty, the number of ways to place 7 balls in 4 bins, leaving exactly 2 (but any 2) empty is ${\displaystyle 6\cdot f(7,2)}$.

Likewise, there are ${\displaystyle 4\cdot f(7,1)}$ ways to place 7 balls in 4 bins with exactly three of them empty. Of course, ${\displaystyle f(7,1)=1}$.

Thus, ${\displaystyle f(7,4)=4^{7}-4\cdot f(7,3)-6\cdot f(7,2)-4\cdot f(7,1)}$

To generalize:

${\displaystyle f(M,1)=1}$

${\displaystyle f(M,N)=N^{M}-\sum _{i=1}^{N-1}{N \choose i}f(M,i)}$ for ${\displaystyle N>1}$, where ${\displaystyle {N \choose i}={\frac {N!}{i!(N-i)!}}}$

It's easier to see with an example; let's look at 7 people and 4 distinct birthdates, so we're looking for ${\displaystyle {\frac {f(7,4)}{g(7,4)}}}$.

${\displaystyle g(7,4)=4^{7}=16384}$

${\displaystyle f(7,1)=1}$

${\displaystyle f(7,2)=2^{7}-{2 \choose 1}f(7,1)=128-2\cdot 1=126}$

${\displaystyle f(7,3)=3^{7}-{3 \choose 2}f(7,2)-{3 \choose 1}f(7,1)=2187-3\cdot 126-3\cdot 1=1806}$

${\displaystyle f(7,4)=4^{7}-{4 \choose 3}f(7,3)-{4 \choose 2}f(7,2)-{4 \choose 1}f(7,1)=16384-4\cdot 1806-6\cdot 126-4\cdot 1=8400}$

Thus, the probability we are looking for is ${\displaystyle {\frac {8400}{16384}}\approx 0.51}$

Chuck 20:09, 27 October 2005 (UTC)[reply]