# Birthday Paradox Variant

Given a population of size $n,$ what is the probability of the event $E$ in which any two people neither share the same birthday nor have birthdays falling on consecutive days?

This problem came up in a recitation for my probability class and didn't really receive satisfactory treatment. I have determined to the best of my abilities that it hasn't appeared in any recent threads.

The way I thought of solving this problem was to consider the complementary event. It seemed reasonable to assume that an outcome would be decided by 1) choosing two days to ignore 2) choose a "starting position" for the first bin (3 choices) and 3) deposit $n$ balls into $\lfloor \frac{563}{3} \rfloor$ bins such that no two balls occupy the same bin. The answer that this gives is $\mathbb{P} (E) = 1 - \frac{3\cdot \binom{365}{2} 121!}{(121-n)! 365^n}.$ I'm pretty sure this is wrong, as you could have a group of 121 people with birthdays staggered by $1$ (eg. Jan 1, Jan 3, ...) Where is the fallacy (and the correct answer?)

-

## 1 Answer

For the answer,

Hint:

1) First find the number of ways to pick $n$ birthdays (from $365$) such that no two are consecutive.

2) Second, once you have such a set, find the number of ways to assign those birthdays to the $n$ people.

Combine and use that to compute the probability.

The answer I get for

1)

$\binom{366-n}{n}$. See this answer on how to derive that: http://math.stackexchange.com/a/102181/1102

2)

$n!$

The final answer

3)

$\frac{n!\binom{366-n}{n}}{365^n}$

-