nPr versus nCr

Greengoblin · #1 $Old$ November 23rd, 2008, 08:03 AM

I understand that for a given combination of n objects, there will be n! permutations, and also understand how there is nPr ways to choose r objects from a combination of n, given by:

$^nP_r=\frac{n!}{(n-r)!}$

I don't however understand what nCr represents, and how it relates to its respective formula, which looks like a simple modification of the formula for nPr. Can someone try to explain? Thanks.

galactus · #2 $Old$ November 23rd, 2008, 08:39 AM

With nCr, order does not matter. With nPr order does matter.

Here is an example I like to use.

Say you have a combination lock. When you turn the dial, the numbers have to be in a particular order. That is a permutation.
If the numbers to open lock were, say, 1-13-25-31.
If it were a combination, you could enter them in any order and it would open.
With a permutation, they have to be in that particular order.
That is why they should be called permutation locks and not combination locks.

Greengoblin · #3 $Old$ November 23rd, 2008, 08:52 AM

Thanks, I get the idea about the difference between a combination and a permutation, and have heard the example about the lock before, but I don't understand it in the context of the formula:

$^nC_r=\frac{n!}{(n-r)!r!}$

for example say we have 10 pictures. If we want to hang 3 on the wall, there are $^{10}P_3$ ways to do so. But I don't get what $^{10}C_3$ gives us.

Is it the number of unique sets of three we can pick from the 10 pictures? I can see how it would be less in this case since some permutations would give the same set of pictures (just in a differet order), but why does this mean we divide by r! ?

Plato · #4 $Old$ November 23rd, 2008, 09:34 AM

Quote:

Originally Posted by Greengoblin $View Post$

for example say we have 10 pictures. If we want to hang 3 on the wall, there are $^{10}P_3$ ways to do so.

Take your own example. There are indeed $^{10}P_3$ ways to form a queue using 3 from 10 different objects. Change the idea. A friend asks you to choose three of the pictures and mail them to him/her. You friend would not know the order in which you selected the three. In fact your friend only cares about the content, the choices, that you made not the order in which you made them. Because three distinct items can be arranged in (3!) ways we divide by (3!) to remove the ordering.
Permutations are order driven, while combinations are content driven.

Greengoblin · #5 $Old$ November 23rd, 2008, 09:44 AM

Ah thanks, it just clicked.