Probability Q: Unordered Draws w/o Replacement

[zeion]

Homework Statement

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)

Homework Equations

The Attempt at a Solution

 

[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!.

 

[zeion]

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

 

[Ray Vickson]

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

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

 

[spamiam]

To expand on what Ray Vickson said:

This is an example of an http://en.wikipedia.org/wiki/Equivalence_relation" . 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.)