# Probability question

1. Sep 22, 2011

### zeion

1. The problem statement, all variables and given/known data

I have a question about the formula for drawing without replacement and considering results to be unordered.

I understand with remembering order it is

n!/(n - k)!

but why do we divide by k! for unordered?
(n is # of different outcome for each draw, k is # of draws)

2. Relevant equations

3. The attempt at a solution

2. Sep 22, 2011

### spamiam

It's to factor out permutations. For instance, if I'm choosing 2 numbers from the set of numbers $\{1,2,3,4\}$ and order is disregarded, then $\{1,2\}$ and $\{2,1\}$ represent equivalent choices. It's a nice exercise to prove that the number of permutations of $n$ distinct numbers is $n!$.

3. Sep 22, 2011

### zeion

How come I have to divide by the repeated choices but not subtract?

4. Sep 22, 2011

### Ray Vickson

Well, suppose n!/(n-k)! = 6,000,000, while k! = 6. Subtracting k! = 6 would leave you with 5,999,994, while the actual number should be 1,000,000; the latter is what we get when we divide by 6, and that is what we should do because there are 6 times as many ordered samples as unordered ones; that is, each distinct unordered sample gives rise to 6 distinct ordered samples.

RGV

5. Sep 23, 2011

### spamiam

To expand on what Ray Vickson said:

This is an example of an http://en.wikipedia.org/wiki/Equivalence_relation" [Broken]. Here's an intuitive example that may help to illustrate the idea. Suppose you have 30 Lego blocks, 10 blue, 10 red, and 10 yellow. Now you decide that you want two blocks to be considered equivalent if they are the same color. So you attach all the blocks of the same color together, leaving you with 3 big Lego blocks, 1 blue, 1 red, 1 yellow. The 10 separate blocks of a given color have been turned into 1 big block.

For a more "math-y" example, consider the set $\{(i,j):1 \leq i \leq 5, \, 1 \leq j \leq 5\}$ of ordered pairs of integers between 1 and 5, of which there are 25. Suppose now that we take two pairs to be equivalent if they have the same first entry. Then $(5,1), (5,2), (5,3), (5,4), (5,5)$ are all equivalent, for instance, so there are only 5 distinct equivalence classes. (Really, we are just left with the numbers 1 through 5, since the second coordinate doesn't matter under the equivalence relation.)

Last edited by a moderator: May 5, 2017