next up previous
Next: Permutations with replacement Up: Introduction to Probability Models Previous: Introduction to Probability Models

Permutations without replacement

If the object selected is not returned to the population before the next object is selected, then an object can appear in the selected subset no more than once. There are n choices in the population to fill the first position, but then that leaves n-1 choices in the population to fill the second position. Therefore, there are $n(n-1)$ ways to fill the first two positions. Continuing this argument, we can see that there are $n(n-1)\dots (n+1-k)$ ways to select k objects without replacement from a population of n objects when selection order is distinguished. This number is commonly expressed using factorial notation,

n(n-1)\dots (n+1-k) = \frac{n!}{(n-k)!}