reply to post by Cryptonic
I don't quite know how to answer. For one thing, I hardly ever concern myself with coincidences/synchronicities which occur in day-to-day life; I have
my hands full with grading, tutorials, papers, that sort of boring stuff
For another, it is often--rather, always--the case that we cherry-pick what is "relevant" and what is not. In fact, even if we read all the history
books... the history books are all cherry-picked! If we could store a sufficiently large and well-distributed set of statistics, we could get a more
conclusive answer.
Here is a page on the coincidences/synchronicities surrounding the number of "elevens" which show
up around the 9/11 incident (plus a deliciously sarcastic retort). In this case I'd venture that we have on the order of 10^7 pieces of
information.
Now, the explanation for those who are lost. It's good that people are curious about it. Maybe it will get people to do more math?

I don't
know.
Say you have some objects, represented by Xs. You have a group of people. Each person is allowed to pick one X. More than one person can pick the same
X. What are the chances that more than one person picks the same X?
For the sake of simplicity, let's have
5 Xs and
2 people.
X X X X X
We can list out all the ways which
2 people can pick from
5 Xs by representing them as sequences of numbers:
11, 12, 13, 14, 15, 21, 22, 23, etc. For example, 42 means the first person picks the 4th X and the second person picks the 2nd X.
You can figure out how many ways there are in total by listing all the ways (there are 25 in total if you list them all out) or calculating. Since
there are
5 choices for each person and
2 people, there are
5^
2 = 25
ways.
This formula works for any
N Xs and
S people. For example, if N = 3 and S = 3 there are 3^3 = 27 ways.
Although 27 is quite small, one would rather not list out all the ways for N = 365 and S = 23. That means it is a good idea to make a formula. And
we have.
Now here's the tricky part. How many ways are there in which more than one person picks the same X? This time we have to dive straight in to the
formula. The trick is to exclude the ways in which
all people pick different Xs.
For the case of 5 Xs and 2 people, the first person has 5 choices, the second person has 4. So we have 5 * 4 = 20. It looks like this listed out: 12,
13, 14, 15, 21, 23, 24, 25, etc. We exclude these ways from the total, so we have 25 - 20 = 5.
For the case of 5 Xs and 3 people, the first person has 5 choices, the second has 4, the third has 3. So we have 5 * 4 * 3 = 60. There are 5^3 = 125
ways in total, so excluding them we have 125 - 60 = 65.
This kind of product, for instance 10 * 9 * 8 * 7, where we start with a number and multiply and decrease over and over, can be expressed using
factorial notation: 3! = 3 * 2 * 1, 4! = 4 * 3 * 2 * 1, and so on. Therefore, 10! / 6! = 10 * 9 * 8 * 7.
Similarly, for the case of
N Xs and
S people, we exclude
N! / (
N -
S)! ways.
To put it all together:
There are N! / (N - S)! ways to exclude
There are N^S ways in total
After excluding, we get N^S - N! / (N - S)!
Dividing by the total number of ways, we get (N^S - N! / (N - S)!) / N^S
Simplifying to 1 - N! / ((N - S)! * N^S)
Which is the collision function stated in the OP.
The birthday paradox is just a "surprising" result obtained from plugging in N = 365 and S = 23 into the collision function.
As an aside... how do people expect to wrap their heads around the serious stuff like astrophysics, classical thermo- and electrodynamics, and
quantum mechanics while being stumped by probability/combinatorics?edit on 2-5-2012 by Tadeusz because: (no reason given)