Combinatoric Solution To The Birthday Paradox I attempted the following solution to the birthday "paradox" problem. It is not correct, but I'd like to know where I went wrong.
Where $P(N)$ is the probability of any two people in a group of $N$ people having the same birthday, I consider the first few values.
For two people, the probability that they share a birthday is simply $1/365$, not counting leap years. For three people, it is the probability of every combination of two of them "ored" together, which is simply the sum of the probabilities of every combination of two people. Thus,
$$
P(2)=P(AB)=\frac{1}{365}
$$
$$
P(3)=P(AB)+P(AC)+P(BC)=3\times P(2)
$$
$$
P(4)=P(AB)+P(AC)+P(AD)+P(BC)+P(BD)+P(CD)=6\times P(2)
$$
Where $P(XY)$ is used to denote the probability of persons $X$ and $Y$ sharing a birthday. You can see pretty clearly that the coefficients are binomial.
$$
P(N)=\binom{N}{2}\times P(2)=\frac{N!}{2!(N-2)!}\cdot\frac{1}{365}=\frac{N(N-1)}{730}
$$
Now according to the pidgeonhole principal, we should have $P(366)=1$, which this expression clearly violates (instead it gives $P(366)=183$). So clearly I'm doing something wrong.
 A: You are over-counting the cases where three people or more share a birthday.
You are also over-counting the case were $A$ and $B$ have the same birthday and $C$ and $D$ have the same birthday.
If $A, B, C$ have the same birthday, then you've counted that case $3$ times, when you only want to count it once. It gets even messier for $4$ ore more with the same birthday, and as $N$ gets larger, that is more and more likely.
It is much easier to calculate the probability that nobody shares a birthday, then subtract that value from $1$.
What you've computed is the expected number of pairs that have the same birthday.
(I just ran 10,000 simulations generating $366$ numbers from $1$ to $365$ and counting equal pairs, and the average number of pairs was $183.12$, pretty close to your $183.$
A: $\def\hor{\ \hbox{or}\ }$Continuing your notation, write $P(ABC)$ for the probability that $A,B$ and $C$ share a birthday.  We can also write something like $P(ABBC)$, but it is the same as $P(ABC)$.  By the principle of inclusion/exclusion we have
$$\eqalign{P(3)
  &=P(AB\hor AC\hor BC)\cr
  &=P(AB)+P(AC)+P(BC)-P(ABAC)-P(ABBC)-P(ACBC)+P(ABACBC)\cr
  &=P(AB)+P(AC)+P(BC)-P(ABC)-P(ABC)-P(ABC)+P(ABC)\cr
  &=P(AB)+P(AC)+P(BC)-2P(ABC)\cr
  &\ne3P(2)\ .\cr}$$
Formulae for $P(4)$ and so on can be worked out in a similar way, although, as pointed out by others, this is not the easiest way to solve the problem.
