How Many Distinct Birthdays in a Room of k People?

[mXSCNT]

This is a restatement of the vocabulary problem which I introduced in https://www.physicsforums.com/showthread.php?t=293553. Perhaps these terms will be more familiar/less ambiguous.

Suppose we are on a planet where each year has n days, and in a room with k people. If birthdays are uniformly distributed throughout the year, how many distinct birthdays, j, do we expect to find in the room? (Alternatively, how many birthdays n-j are NOT represented in the room, on average?)

 

[mXSCNT]

Here's the answer (someone else's idea): j = n - n * (1-1/n)^k. The probability that a given day is nobody's birthday is (1-1/n)^k, so the expected number of days that are nobody's birthday is n * (1-1/n)^k.

 

[ToxicBug]

I think that, since its distinct birthdays (from what I understand, distinct bdays are only the ones that don't coincide on the same day), you will have nCk bdays total, thus the expected number on any given day would be (nCk)/n since they're uniformly distributed.

There will also be nC(n-k) bdays that don't happen, once again the expected number would be nC(n-k)/n since they're uniform. I'm not sure about this, but I think its intuitive.

 

[AKG]

Let X be the number of distinct birthdays, and for $1 \leq i \leq n$ define X_i to be 1 if there's at least one person whose birthday is on the ith day, and 0 otherwise. Then X = X₁ + X₂ + ... + X_n, so:

$$E(X) = \sum _{i=1} ^n E(X_i) = nE(X_1)$$

E(X₁)
= Prob(at least one person has their birthday on day 1)
= 1 - Prob(no one has their birthday on day 1)
= 1 - (# of ways to arrange k birthdays amongst n-1 days, allowing repetition)/(# of ways to arrange k birthdays amongst n days, allowing repetition)
= $1 - \binom{n+k-2}{k} / \binom{n+k-1}{k}$

So the final answer is:

$$\frac{nk}{n+k-1}$$

 

[ToxicBug]

define X_i to be 1 if there's at least one person whose birthday is on the ith day, and 0 otherwise.

But doesn't the question as for distinct birthdays, ie Xi would be 1 if there is only one birthday on day i and 0 if there is not only one birthday on day i?