The Birthday Problem:
If I am partying in a room with 25 people; what is the chance that NO two of those people will share a birthday?
Another way to phrase this: When given 25 random people, what is the chance that for every day of the year, either one or zero of those people will have a birthday on that day.
The Birthday Solution:
For simplicity's sake, we will assume that all days of the year are equally likely to have birthdays fall on them.
For simplicity's sake, we will also ignore leap years, and thus leap days.
Since each person could have a birthday on any day of the year, in total there are 365 ^ 25 possibilities.
But how many of those 365 ^ 25 possibilities will satisfy the requirement that no two people may share a birthday?
You can think of it like this: Person-A has 356 days to choose from. Person-B only has 364 days to choose from without conflicting with person-A's choice. Person-C has 363 choices, and so on and so forth.
Right now we have two numbers: 365 * 364 * 363 . . . * 343 * 342 * 341 simplifies to 365! / 340! which is the number of possibilities that work, and 365 ^ 25 is the total number of possibilities.
By using division, and then multiplying by 100, we come to a percentage: 43.18%
The Birthday Problem 2.0:
Because everybody likes me, I am partying in a room with 170 people; what is the chance that NO four people will share a birthday?
Another way to phrase this: When given 170 random people, What is the chance that for every day of the year, no more than three of those people will have a birthday on that day.
The Birthday Solution 2.0:
I was going to try to explain my program, but I am not that good at explaining things, so here is the C code.
int stopfact( int pier, int depth ) { int retval = 1; for( int i = 0; i < depth; ++i ) { retval *= pier; --pier; } return retval;}double power( double base, int exponent ) { double retval = 1.0; for( int i = 0; i < exponent; ++i ) { retval *= base; } return retval;}#include <stdio.h>#include <stdlib.h>int main() { int bucket_count = 0; double * buckets; double chance_total = 0.0; int copies; double frequency; while( scanf( "%i %lf", & copies, & frequency ) == 2 ) { buckets = realloc( buckets, sizeof( double ) * ( bucket_count + copies ) ); for( int i = 0; i < copies; ++i ) { buckets[ bucket_count ] = frequency; ++bucket_count; chance_total += frequency; } } int balls; int limit; double * chancetable; double * newtable; scanf( "?> %i %i", & balls, & limit ); chancetable = malloc( sizeof( double ) * ( balls + 1 ) ); newtable = malloc( sizeof( double ) * ( balls + 1 ) ); chancetable[ 0 ] = 1.0; for( int i = 1; i <= balls; ++i ) { chancetable[ i ] = 0.0; } for( int i = 0; i < bucket_count; ++i ) { for( int u = 0; u <= balls; ++u ) { newtable[ u ] = 0.0; } for( int u = 0; u < limit; ++u ) { for( int z = 0; z + u <= balls; ++z ) { newtable[ z + u ] += chancetable[ z ] * ( double )( stopfact( balls - z, u ) / stopfact( u, u ) ) * power( buckets[ i ] / chance_total, u ) * power( ( chance_total - buckets[ i ] ) / chance_total, ( balls - z ) - u ); } } for( int u = 0; u <= balls; ++u ) { chancetable[ u ] = newtable[ u ]; } chance_total -= buckets[ i ]; } printf( "%lf %\n", chancetable[ balls ] * 100.0 ); free( buckets ); free( chancetable ); return 0;}
To see the answer for yourself, run the program and input the following:
365 41 1?> 170 4
If you made sure to space separate, the result should be: 61.30% accounting for leap years too.
