An efficient function

Let's consider the function : F (b ; n) = b!/[(b-n)!b^n]
This function gives the probability to have, in base b and in n occurrences, none repetition.

Here are three examples of application :

• Let's take four consecutive digits out of a random number. The probability that these four digits have four different values is given by F (10 ; 4) = 504/1000. So there is a probability 496/1000 (nearly 0.5) that one digit is present minimum twice.


• In a throw of five dices, what is the probability to get a sequence (a sequence is 1, 2, 3, 4, 5 or 2, 3, 4, 5, 6)? The probability to get five different values is given by F(6 ; 5) = 5/54. We have a sequence when the missing digit is either 1 or 6, and that happens one time out of three. The probability of a sequence is 5/162 ( about 0.03).


• The "birthdays paradox" :
  n persons are in a room (we assume that the days of birthday are uniformly distributed on the year, and February 29th is not taken into account.)
  What is the minimum value of n for which the probability that minimum two people have the same day of birthday (example: January 7th - we don't take the year into account) is higher than 0.5?
  The probability to have n different dates is F (365 ; n).
  F(365 ; 23) = 0.493. For n >= 23, the probability to have at least one repetition is > 0.5, and the answer is 23.