Hello! Thanks for the fun puzzle! Believe it or not, this is only the first or second time I've done one of these puzzles, despite getting the TR for two years now.

I think the solutions goes as follows:

We are taking a year to have d=365 days. There are d^d total ways that d people have their birthdays distributed (each person has d possibilities and they are independent).

Consider one choice of possible birthdays—you can think of this as a list of length d, where each entry is an integer between 1 and d. If you were to make a tally of the numbers appearing in this list, you would be *partitioning* a set of d people into their k unique birthdays.

We want to know: How many ways are there to arrive at a partition of d people with k unique birthdays? This is known as the Stirling number of the second kind, S(d,k).

Ok, now let's ask how many ways are there to distribute these k unique birthdays throughout the year—keeping in mind that the order of the parts is important. This is simply d P k = d! / (d-k)!.

Thus the total number of ways that you can get k unique birthdays is the product

$\frac{d!}{(d-k)!} S(d,k)$ .

As a check, the sum of the above from k=1...d indeed gives d^d, which is all the possible choices of birthdays.

Now we're ready to do the expectation value. The expectation value of k unique birthday is

$\langle k \rangle = \sum_{k=1}^d k \cdot \frac{1}{d^d} \frac{d!}{(d-k)!} S(d,k)$ .

Now taking d=365, we get the unwieldy fraction:

<k> =

109154572075978613283744835037559287287576786746462629439277411488882541310200\

538491800868943970011546165607556635754445120470309535814221894547316834707823\

364004569059333835804445615715576408111425882359986057854580549064112836493004\

226296388960471198463228030348923170080924423482241610275697637546755174477688\

199761041817991030722457984450400549437638983076541172078685533436072231846666\

034047896126921802680340629063049786737954218729685538396826030975957806114818\

431293028971557398623617719510517189558681463229993995462298386104044364551312\

771028561012301053350792803220414708777980152397900531320568324839576271455536\

797100670817782358676589663868948035567780640548008423385762632363785125498676\

353129028760500849852833483276032912927416017557254073261526265281711200750887\

105236283610920657757813497907678981547330420097858838225179870773683868744745\

905020893977325903194410355689960568014013674616171257610824051546696434967901\

/47271856885513078783533109496869551999090365583145040927571182974935408283248\

320690130244467809204791100240425828054910518056088897318665584453855269731987\

057951357594325164935687652751144283127437040802435355937386317264098530363358\

626053723250568673764266453544651412818395473544739369746652280633130799028726\

071124205795236410874798213029355626223257181154374286985905727361325467563904\

017739554977501348259982216047485307566634333868999841296838188120135133465292\

731819966827994293775299134056420586719416085458199179722693937034212295248091\

247794318359538985788961956012666757478659056353195928022881985271298995528837\

150334990135790439615639882784673479537736912989551179118824447742302490566126\

814100494247855395441346082542865084926968628774746290546572917795258640950929\

016606903069086980556066482551239885930565911693845475873745221041360810583042\

5126825579471846407023247227204205446471352303206003853119909763336181640625.

This is approximately <k> ~ 230.908.

Leo Stein