Probability of Adjacent Birthdays

Question

Recall the birthday problem, where only 23 people are required for a >50% chance that at least two share the same birthday.

What is the new probability if we want at least two people out of twenty-three to share the same birthday or have adjacent birthdays? January 1 and December 31 are considered adjacent, and we don't consider February 29.

Similar to the birthday problem, I thought it would be easier to consider the probability that nobody has matching or adjacent birthdays, but as I was setting up the products, I realized that there are different amounts of available dates, depending on when the birthdays are. For ease of writing, let the dates be represented as 1, 2, 3, 4, ..., 365. Say the first person's birthday is 1. If the second person's birthday is 3 or 364, then there are 360 remaining choices for the third birthday, but if the second person's birthday is not in (364, 365, 1, 2, 3), then there are 359 remaining choices for the third person's birthday. Considering all these possibilities for 23 people is tedious, however.

I also tried approaching this from a stars and bars perspective. Arrange 23 bars in a circle, put one star automatically between each bar, leaving 339 possible dates to be inserted. However, this also is difficult because there's an ordering. If three bars are Mar 1, Mar 14, and Mar 20, you can't stick Aug 5 in there. So, I was at a loss to figure it out intuitively.

On the other hand, I generated a pattern by starting small (5 days and 2 people, for example), and finding a function out of OEIS. The answer to the problem with 365 days and 23 people is

$$1 - \frac{23!}{365^{23}} \left( \binom{343}{23} - \binom{341}{21} \right) \approx 0.8879096$$

Let $r(n,k)$ be the rising factorial, $n(n+1)(n+2)...(n+k-1)$. The answer can also be written as

$$1 - \frac{23!}{365^{23}} \left( r(321, 23) - r(321, 21) \right) \approx 0.8879096$$

The $321$ comes from $365 - 2(23-1)$, which is due to the pattern I found.

My question is, what's the intuitive way to approach this problem, or how do I actually derive the formula to get my answer?

Answer 1

Without loss of generality break the circle of days at the first person's birthday, leaving a row of $364$ days. We want to count the number of ways $n-1$ other, different birthdays ($n$ people total) can be filled into those slots so no two birthdays are adjacent to each other or the row's ends.

The $n-1$ other people may be viewed as bars dividing the row into $n$ necessarily nonempty parts and the $365-n$ unfilled days as stars; there are thus $364-n$ places the bars can go into and the desired number is $\binom{364-n}{n-1}(n-1)!$ when the people's order matters. The number of ways to assign birthdays in order without restrictions, keeping the first person's birthday fixed, is $365^{n-1}$. The probability of no birthdays adjacent is therefore $$\frac{(364-n)!}{365^{n-1}(365-2n)!}$$ which is $0.11209035633\dots$ for $n=23$ (agreeing with your result) and first less than $\frac12$ for $n=14$.

Answer 2

The problem may be elegantly attacked by re-construing the original Birthday problem to be a Stars and Bars problem, and then regarding this problem as a refinement of the original problem.

For Stars and Bars theory, see this article and this article.

---

Thank goodness that you made the simplifying assumptions that Dec 31 is right-next-to Jan 1, and that Feb 29 does not exist.

First consider the original problem by regarding the dates of the $(23)$ people as

$$D_1, D_2, \cdots, D_{23}.$$

Then, in the original problem, the probability may be regarded as $$\frac{N}{D} ~: ~D = 365^{23}.$$

In the original problem, you would then consider the number of non-negative integer solutions to

$$x_1 + x_2 + \cdots + x_{24} = (365 - 23). \tag1 $$

In (1) above, the $(24)$ variables may be regarded as the gaps before and after the $(23)$ dates, $D_1, D_2,\cdots, D_{23},$ which are required to be distinct dates in strictly ascending order.

Per Stars and Bars theory, the enumeration of the number of solutions is

$$\binom{[365 - 23] + [24 - 1]}{[24 - 1]} = \binom{365}{23}. \tag2 $$

Note that (2) above gives the perfect enumeration of the numerator in the original problem, except that the enumeration is lacking the $(23!)$ factor, which represents that the $(23)$ people can be assigned the dates $D_1, \cdots, D_{23}$ in $(23)!$ ways.

---

The only necessary alteration to the Stars and Bars approach of the original problem is that:

• Each of $~\displaystyle \left(x_2, x_3, \cdots, x_{23}\right)~$ must be $\geq 1 ~~~$ and

• Either $~x_1 \geq 1, ~~x_{24} \geq 1,~$ or both.

The two bullet-pointed complications above are handled as follows:

$y_i = x_i - 1 ~: ~2 \leq i \leq 23.$

This implies that you want the number of non-negative integer solutions to

$$~\color{red}{x_1} + y_2 + \cdots + y_{23} + \color{red}{x_{24}} = [365 - 23] ~\color{red}{- 22}. \tag3 $$

The enumeration to (3) above, which may be construed to be $N_1,$ which will represent a partial computation in the numerator of the refined problem, is calculated as

$$\binom{[\langle 365 - 23\rangle - 22] + [24 - 1]}{[24 - 1]} = \binom{343}{23}. \tag4 $$

So, you have that

$$N_1 = \binom{343}{23},$$

which represents the enumeration when $x_2, \cdots, x_{23}$ are all forced to be $\geq 1$, and represents that there must be at least one day between each of $D_1,D_2$ and $D_2,D_3$ and ... and $D_{22},D_{23}.$

What I need is to use $N_1$ as a baseline computation, and deduct from that all of the situations where $x_1$ and $x_{24}$ are both equal to $(0)$.

The number of solutions to deduct will be the number of non-negative integer solutions to

$$0 + y_2 + \cdots + y_{23} + 0 = [365 - 23] - 22.$$

This computation will be

$$N_2 = \binom{[\langle 365 - 23\rangle - 22] + [22 - 1]}{[22 - 1]} = \binom{341}{21}. \tag4 $$

So, the final enumeration of the numerator will be

$$N = N_1 - N_2 = \binom{343}{23} - \binom{341}{21}. \tag5 $$

Then, using (5) above, the final computation will be

$$\frac{(23)!}{(365)^{(23)}} \times N.$$

Answer 3

• Make $23$ blocks of birthday - nonbirthday, $(365-23) =342$ entities result
• Place the $23$ blocks in $\binom{342 }{23}$ ways
• Multiply by $\frac{365}{342}$ as you allowed birthdays only $342$ starts
• Finally multiply by $23!$ to assign people to birthdays and divide by all possible assignations, $365^{23}$
• P(some birthdays shared or adjacent) $ = 1 - \Large\dfrac{23!\cdot\frac{ 365}{342}\cdot\binom{342}{23}}{365^{23}}$

---

Added Explanation

The total possible birthdays of $365^{23}$, and the final use of the complement are yours, I shall explain the numerator.

• Form blocks of birthday-nonbirthday, $\;\boxed{BN}....\boxed{BN}\,$ (clockwise,say) to ensure that no two birthdays are adjacent in the circle

• The placing of the blocks in $\dbinom{365-23}{23} = \dbinom{342}{23}\;$ ways, and $23!$ for who occupies which of the $23$ birthdays should be obvious

• The unusual feature in the approach is to circumvent stars and bars by forming blocks, and correcting for the reduced starting points now available for birthdays by the multiplier $\Large\frac{365}{342}$