The paradox of birthdays for three people

Many people know the paradox of birthdays : in a group of 23 randomly selected people, the probability that at least two of them have a matching birthday exceeds 1/2.

The problem that I will consider is formulated as an exercise in the book Algorithms: construction and analysis :

“How many people need to take to meet with the same probability 1/2 at least three with a matching birthday.”

Immediately, we note that the birthdays of experience participants, as events, are considered jointly independent and equally probable.

We introduce some notation:
')
n = 365 (leap year is also omitted).
k - the number of participants. We assume k <= 2 n , otherwise triple coincidence will happen with probability 1.

A - an event consisting in the fact that in the group there are three or more people with the same birthday.
B = ( not A ) - an event consisting in the fact that no three participants have the same birthday.

Event B will be performed if and only if exactly two participants will fall on a certain number of m different days in a year, and on the other ( k - 2 m ) days there will be exactly one person:

Days	d 1	d 2	...	d k - 2 m	d k - 2 m +1	d k - 2 m +2	...	d k - m	d k - m + 1	...	d n
Number of persons	one	one	...	one	2	2	...	2	0	...	0

It is clear that m can vary depending on a specific group of people from 0 to [ k / 2].
We denote B _m - an event consisting in the fact that there are exactly two participants for m different days in a year, and one for each other ( k - 2 m ) days.
The peculiarity of the set of events { B _m , m = 0, ..., [ k / 2]} is that they are incompatible and

B = B ₀ ∪ B ₁ ∪ ... ∪ B _{[ k / 2]} .

This enables us to calculate the probability of an event B in terms of the probabilities of events B _m :

P ( B ) = P ( B ₀ ) + P ( B ₁ ) +… + P ( B _{[ k / 2]} ).

Next we will look for the probability of events B _m .

Equiprobable elementary outcomes (events) will be sets of pairs: {( i , d _i ); i = 1, ..., k }, each of which means that person number i has d _i as a birthday.
The number of all elementary outcomes is determined based on the fact that each participant has n birthday options:
N _{B m} = n ^k .

The number of elementary outcomes when the B _m event is executed is considered somewhat more complicated:

B _m = C _n ^m C _nm ^{k -2 m} k ! / 2 ^m .

Here we first determine the number of ways that m days for double matches can be selected. Then from the remaining days choose k - 2 m , which accounts for one person. On selected days, participants can accommodate k ! / 2 ^m ways. Divide by 2 ^m , because we don’t care about the order inside couples who have a common birthday.

therefore

P ( B _m ) = N _{B m} / N = C _n ^m C _nm ^{k -2 m} k ! / (2 ^m n ^k ).
P ( B ) = k ! (C _n ⁰ C _{n -0} ^{k -0} / 2 ⁰ + C _n ¹ C _{n -1} ^{k -2} / 2 ¹ + ... + C _n ^m C _nm ^{k -2 m} / 2 ^m + ... + C _n ^{[ k / 2]} C _{n - [ k / 2]} ^{k -2 [ k / 2]} / 2 ^{[ k / 2]} ) / n ^k .

The required probability will be equal to:

P ( A ) = 1 - P ( B ) = 1 - k ! (C _n ⁰ C _{n -0} ^{k -0} / 2 ⁰ + C _n ¹ C _{n -1} ^{k -2} / 2 ¹ + ... + C _n ^m C _nm ^{k -2 m} / 2 ^m + ... + C _n ^{[ k / 2]} C _{n - [ k / 2]} ^{k -2 [ k / 2]} / 2 ^{[ k / 2]} ) / n ^k .

My Java program produced the following values ​​of this probability depending on k :

k	P ( A )
2	0
3	7.506E-6
five	7.475E-5
ten	8.877E-4
20	0.00824
40	0.0669
60	0.207
70	0.306
80	0.418
87	0.499
88	0.511
100	0.646
110	0.746
120	0.828
150	0.965
200	0.999512
250	0.999999460

So, you need at least 88 people so that the probability of triple coincidence exceeds 1/2.