1
$\begingroup$

If I have a total of n different items to choose from (example, sides of a die), and I continually choose an item from the set (example, roll the die), is there a way to calculate the odds of having hit a duplicate after having choosen k elements (example, k die rolls) without using factorials?

I've worked it out to the following: \begin{equation}n!/(n-k)! n^k\end{equation}

The problem is that this calculation becomes unruly with big numbers. If I was interested in the odds of hitting a duplicate from a set of 10 million after 500 draws, then this would equate to: \begin{equation}10000000!/(9999500!*10000000^{500})\end{equation}

Is this kind of equation realistic to calculate? A colleague quoted such a probability one time and I was curious how he had calculated it.

$\endgroup$
2
  • $\begingroup$ There are various ways to approximate. For your problem, there is some useful information here. $\endgroup$ Commented Jan 7, 2016 at 21:50
  • $\begingroup$ The most famous one is stirlings approximation for factorials. $\endgroup$ Commented Jan 7, 2016 at 21:51

1 Answer 1

Reset to default
0
$\begingroup$

You can calculate $\frac{n!}{(n-k)!n^k}$ with the following pseudocode :

x:=1 For j=1,...,k x:=x * (n+1-j)/n

Then, $x$ has the desired value. This should work even for very large numbers.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.