Birthdays

Call event $A$ the event that at least 2 people out of $k$ share the same birthday.  The probability of this is one minus the complement  $A^c$, namely that all $k$ individuals have different birthdays.  This is easier to calculate using permutations and counting methods. The answer is $1 - \frac{365!}{365^k(365-k)!}$  To break this apart, you're finding the number of ways in which you can permute $k$ from $365$, which is $365 \times 364 \times ... \times 365 -k$.  You divide this by the total number of days of the year each of $k$ people could conceivably have their birthday, in an unconstrained way.  This is simply $365 \times 365, k$ times, or $365^k$.  Generalising this away from dates, you get $1 - n!\binom{n}{k} \frac{1}{n^k}$.  Selecting $k$ people like this is at base a kind of sampling without replacement.  How does one solve a problem like this.  The first step is to realise that solving its complement may be more tractable than solving the primary problem. This trick is as old as the origins of probability theory itself - see how Pascal used it for DeMere's foundational gambling problem.

 Secondly, the basic law of sampling with replacement, namely the act of picking $k$ from $n$ with replacement can be done in $n \times n \times n ... \times n, k$ times, or $n^k$ for short.  This is the free and unconstrained selection of $k$ objects each of which can have one of $n$ attributes.  Then with this denominator counted, you work out the top line, namely the ways in which you can have $k$ all of whom have different birthdays.  This would be sampling with replacement, also known as a permutation, on the numerator.  Perhaps $1-n!\frac{\binom{n}{k}}{n^k}$ is clearer. Permutation is the act of creating a list from a set.

To get to this point mathematically you're simplifying reality. No twins considered, no increased school prevalence of joint birthday parties, no modelling of the non uniform distribution of birthdays throughout the year. The birthday problem appears in most probability textbooks.  But now to find alternative uses for it and to come to a conclusion about the implementation of factorial in systems.

There are 2 dimensions to this problem - first you take a sample of $k$ objects, presumably from a larger population.   This act of sampling is assumed to be completely uniform - namely that the likelihood of you having picked this object is considered to be the same as the likelihood of any other object. Notice that we don't have (or need) a handle on the size of the population.

The second dimension to the problem implies that every member of your population has been deterministically classified.  And further, that this categorisation has a finite (or countably infinite) range of possibilities and that this categorisation can be mapped onto a a counting label. With birthdays, you can be sure that whoever you pick, they were surely born on one of 365 dates of the year. The cardinality of this categorisation  is of course 365. Be clear however that the categorisation itself doesn't have to be inherently numeric, since you're attaching a cardinality to the categorisation.  What I mean by this can be spelled out with another example. We could create a palette of 50 colours and for every member of the population map their eye colour to one of those 50 colour buckets. Clearly there's no inherent numerical or ordering aspect to these 50 colours yet we know that there are 50 of them. Notice here that with eye colour it is unlikely that the bucketing would be as uniformly distributed as the putative day of year was. Without the uniformity of the bucketing distribution you wouldn't arrive at the birthday solution but would need a more complex solution.

So let's step back. We need a categorisation which - unlike many real world categorisations, which are probably likely to be distributed by some kind of power law distribution - is uniformly distributed over the population.

Condition 1 says we implicitly pick $k$ objects with uniform likelihood from a population. Condition 2 says that the population must be categorised in a perfectly uniform way.  Without condition 2 you don't get a denominator with $n^k$ in it.

What kind of categorisation is so perfectly uniformly distributed? How could it be so? Real world informationally contentful categorisations are rarely so uniform. Using the technical definition of information however, random categorisations are indeed the most informationally rich - they reduce the largest amount of uncertainty when the categorisation is revealed to you.  Even if the categorisation is deterministic for the objects, you still, in selecting $k$ from the population, might chose any number of repeats.  This probability calculation tells you how likely you are to achieve 'all clear' or not.

I must link these 2 dimensions together - you don't need the sampling process to have an unconditionally uniform likelihood of picking any member. It only needs to be uniform with respect to the categorisation, that is conditional on the particular categorisation you've chosen. In other words the selector of the sample might be quite non-uniform provided that the categorisation probability distribution is such that the probability of having selected any one object times the conditional probability of picking a category given the object works out as uniformly distributed.

OK so with this in mind I'd like to consider other examples of the birthday problem.

Start with a binary classification.  Say boys and girls - probability examples often  make the approximating assumption that they're equally likely in the population. Let's say we pick two people at random.  What are the chances that the two people are of the same sex?  Clearly this ought to be $\frac{1}{2}$.  Let's see:  $\frac{2\times 1}{(2^2)(0!)} $.

How about good old dice.  I have a game with a single die.  A play fee of $1$ is associated with the game where the player throws 3 times in a row and if the same number comes up you win.  If you were going to devise this as a break-even profitable game, what reward ($r$) can you afford to give to the gambler?  $1- \frac{6 \times 5 \times 4}{6^3}$ or $1-\frac{120}{216}$ which equals $0.444$ or 44.4%.  So $0.444 \times r = 1$.  Hence $r=2.25$ is a break-even level of reward.

A ticket machine allocates tickets for passengers to travel on a 20 carriage train such that it allocates the passenger to a carriage uniformly.  5 Drunken Irish men buy tickets.  What are the chances that at least two of them end up in the same carriage, at which point they will start singing sad ballads loudly together?  The answer is $1-\frac{20 \times 19 \times 18 \times 17 \times 16}{20^5}$ or $1-\frac{1,860,480}{3,200,000}$ or $1-0.5814$ or $0.42$ approximately, a 42% chance.

You have in your hands a digital contract.  And a fraudulent one which benefits you.  You have also access to the same hash function used by some cryptographic community - e.g. a bitcoin pay hash or a pgp hash.  Now in a legitimate process, this hashed contract would be signed by the patsy's private key (which you don't have).  So what you do is make a large number of informationally identical but subtly different copies of the legitimate contract and a large number of similar copies of your putative fraudulent contract.  Keep producing new alternatives on both sides until finally you find one such that both the legitimate and the illegitimate evaluate to precisely the same hash.  The collision you found is much easier than you might imagine, thanks to the birthday problem.  Once found, you submit the legitimate contract to the patsy.  The patsy signs this.  You scrape away the digital signature and attach it to the same-hash-producing illegitimate contract, benefiting you.  Present this for payment and you will have exploited the patsy.

You have to estimate the population of sparrows in a woodland area but you're on a budget.  You catch 100 sparrows, tag them with 'TPS' for 'The Persistent Struggle' then release them again.  A week later you return and you catch another 200.  Of these 200, 6 had TPS tags (3% or 0.03).  So you estimate the population in this woodland as 100/0.03 or 3,333 sparrows.

The following link contains some history on the birthday problem.

The Problem of Points - Symbols

Christian Kramp invented the usage of the symbol ! to represent factorial.  The idea of $n(n-1)(n-2)..2.1$ as an interesting product which represents all the ways that n unique and completely distinct objects can be permuted dates to at least the 12th century.  To show this is the case imagine the following thought experiment.

Imagine that a man walks into one of the world's most sumptuous brothels.  His reward was to have a sexual encounter with every available woman in the brothel.  He enters a room filled with seven of the most desirable women he has ever seen.  One has jet black hair, is nearly six feet tall and has a full and firm ass.  Two is smaller with short black hair and a wicked twinkle in here eye.  Three is central Asian looking, small perfectly formed breasts.  Four is from south east Asia, an imperturbable and fiercely independent soul.  Five is from central Europe, innocently cheeky.  Six is from the Caribbean  tall and rangy.  He knows that he will fuck them all.  He picks number one, goes with her, comes back, picks number three this time.  Repeats until he is done.  This is a permutation.  A single permutation.  How many ways could he have chosen?  The answer is 6!, which   is 720.  He could have had 720 chronologically different sexual experiences.

Imagine you are him.  Imagine his decision moments.  His first decision was to pick the tall jet black haired girl.  This was a so-called free choice.  A choice of one in six.  Immediately start imagining a total of six parallel worlds.  In each world, he started with one or another of the six girls.  OK.  Focus on his reality again.  In the real world, he now has to chose which one of the five remaining girls to fuck.  Now, in each of the 6 parallel worlds, he'll similarly need to make a 1 in 5 choice.  So for each and every one of the 6 imagined worlds, a further multiplication of 5 occurs.  There are now 6 times  5 or thirty worlds which capture all the possibilities he has to chose from.  Repeat and you will find 720 different worlds.  In making his particular ordering choice,  he in essence picked one of 720 different worlds.

Without knowing the man, his sexual preferences, etc, if we had to guess his selection we could imagine each of the 720 worlds was equally likely to be chosen.  That is, you might say that the likelihood of choosing the fucking order of <tall-dark then short dark then central Asian then SE Asian then central European and finally Caribbean> was $\frac{1}{6!}$. 

Insofar as every object is uniquely distinguishable from every other object, then this idea of permutations is quite core to the most basic choosing activity - their ordering.  Visually you can see this as lining them up in a particular way, touching them in a particular, order, placing them sequentially on a particular chronology.

Imagine you got to know that some kind of selection process has 1,000,000 different distinct possibilities, the final result being a collection of 6 uniquely distinguishable objects.  Well, if you didn't actually care about the ordering your set of possibilities would be reduced down to $\frac{1000000}{6!}$.  Imagine you needed to pick 6 women to come on a journey with you.  Someone informs you that the selection process imposed on you allowed you to pick a particular order-important set of 6 women with equal chances $\frac{1}{1000000}$.  But you know that it doesn't matter to you what order they got picked.  They're coming with you all the same.  In this case, you'd divide your million possibilities by 6!.  Thus $\frac{6!}{1000000}$ is the likelihood of picking those 6 women (or indeed any 6 women).  Here you're using the permutation formula to make order irrelevant.  By knowing the set of choices implied in a strict ordering, you can use that knowledge to throw away the importance of ordering.

Klamp chose the word 'factorial' because it sounded more French than its rivals.