Extending the birthday paradox to more than 2 people In the traditional Birthday Paradox the question is "what are the chances that two or more people in a group of $n$ people share a birthday".  I'm stuck on a problem which is an extension of this.
Instead of knowing the probability that two people share a birthday, I need to extend the question to know what is the probability that $x$ or more people share a birthday.  With $x=2$ you can do this by calculating the probability that no two people share a birthday and subtract that from $1$, but I don't think I can extend this logic to larger numbers of $x$.
To further complicate this I also need a solution which will work for very large numbers for $n$ (millions) and $x$ (thousands).
 A: It is always possible to solve this problem with a monte-carlo solution, although that's far from the most efficient.  Here's a simple example of the 2 person problem in R (from a presentation I gave last year; I used this as an example of inefficient code), which could be easily adjusted to account for more than 2:
birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}

A: This is an attempt at a general solution. There may be some mistakes so use with caution!
First some notation:
$P(x,n)$ be the probability that $x$ or more people share a birthday among $n$ people,
$P(y|n)$ be the probability that exactly $y$ people share a birthday among $n$ people.
Notes:


*

*Abuse of notation as $P(.)$ is being used in two different ways.

*By definition $y$ cannot take the value of 1 as it does not make any sense and $y$ = 0 can be interpreted to mean that no one shares a common birthday.
Then the required probability is given by:
$P(x,n) = 1 - P(0|n) - P(2|n) - P(3|n) .... - P(x-1|n)$
Now,
$P(y|n) = {n \choose y} (\frac{365}{365})^y \ \prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$
Here is the logic: You need the probability that exactly $y$ people share a birthday. 
Step 1: You can pick $y$ people in ${n \choose y}$ ways.
Step 2: Since they share a birthday it can be any of the 365 days in a year. So, we basically have 365 choices which gives us $(\frac{365}{365})^y$.
Step 3: The remaining $n-y$ people should not share a birthday with the first $y$ people or with each other. This reasoning gives us $\prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$.
You can check that for $x$ = 2 the above collapses to the standard birthday paradox solution.
