Combinations and Permutations

Due to math content, this page has special requirements (including JavaScript) for full functionality.
With your current viewing scenario, it is not appearing and behaving as it is supposed to!
Please visit Dr. Carol J.V. Fisher's Homepage to learn what this site has to offer.
Watch the "Welcome" video to get started—hope to see you back here soon!

Dr. Carol J.V. Fisher's Homepage

For this exercise, you need ♥ INTERNET EXPLORER 6.0 and above, with MathPlayer installed.♥

COMBINATIONS AND PERMUTATIONS

Jump right to the exercises!

Recall from a previous section ( Choosing Things: Does Order Matter?)
that Ckn denotes the number of ways to choose k items from n (without replacement) when the order DOESN'T matter;
it is the number of combinations that are possible when choosing k items from n items.

Also, Pkn denotes the number of ways to choose k items from n (without replacement) when the order DOES matter;
it is the number of permutations that are possible when arranging k items that are chosen from n items.

In this section, formulas are developed for both Ckn and Pkn .

GETTING THE FORMULA FOR Pkn
First, an example.
Suppose that five letters are in an urn: A, B, C, D, and E.
You must choose two, without replacement, where order matters.

There are five choices for the first letter.
You don't put this letter back in the urn (since we're choosing without replacement),
so now only four letters are left in the urn.
Thus, there are four choices for the second letter.

By the Multiplication Counting Principle (in the section More Probability Concepts),
the number of possible outcomes is 5 · 4 = 20 .
Here are lots of different names for this number:
P25 =5⋅4= 5⋅4⋅ 3!3! =5⋅4 ⋅3!3! =5! 3!= 5!(5- 2)!
Generalizing this example, we see that:
Pkn =n! (n-k) !
Here are the 20 possible arrangements of two letters chosen from five, where order matters.
Arrangements that use the same letters have the same background color.

AB	AC	AD	AE
BA	BC	BD	BE
CA	CB	CD	CE
DA	DB	DC	DE
EA	EB	EC	ED

GETTING THE FORMULA FOR Ckn
Continuing with the example above, we can now ask the question:
How many ways are there to choose two letters from five letters (without replacement), when the order doesn't matter?

For this question, choosing "A" first and "B" second gives the same combination as choosing "B" first and "A" second.
That is, the outcomes "AB" and "BA" both correspond to the same combination, {A,B } .

When we separate the 20 permutations above into piles of the same color, we get:

AB BA	AC CA	AD DA	AE EA	BC CB
BD DB	BE EB	DC CD	CE EC	DE ED

Each colored pile corresponds to a single combination.
Since there are only 2⋅1= 2 ways to arrange two letters, each colored pile contains 2 members.

Thus, there are total # of permutations # in each colored pile = 202 =10 combinations.

But what if we had chosen three letters from the urn, instead of two?
Then, a typical permutation might look like "DBA".
How many different arrangements are there of these three letters?

Using the Multiplication Counting Principle again, there are 3!=3⋅2⋅ 1=6 : DBA, DAB, BDA, BAD, ADB, ABD.
Thus, in choosing 3 letters from an urn, the permutations would be broken up into piles of size 3! , and

# of combinations=# of permutations 3! .

Generalizing these observations gives the following formulas for permutations and combinations:

FORMULAS FOR Pkn

The notation Pkn denotes the number of ways to choose k items from n (without replacement) when the order DOES matter;
it is the number of permutations that are possible when arranging k items that are chosen from n items.

Let n and k be integers with n≥1 , k≥1 , and k≤n .
Then, either of the following formulas can be used:

Pkn	=  n(n- 1)(n-2 )⋅...⋅( n-(k-1 ))	( k factors)
	=  n! (n-k) !

For k=0 , we define P0n:=1 .

Note that it makes sense that P0n should equal one:
How many ways are there to choose no items from an urn?
Exactly one way—choose nothing!

FORMULAS FOR Ckn

The notation Ckn denotes the number of ways to choose k items from n (without replacement) when the order DOESN'T matter;
it is the number of combinations that are possible when choosing k items from n items.

Let n and k be integers with n≥1 , k≥0 , and k≤n .
Then, Ckn   =  Pkn k!  =  n! k!(n- k)!
Recall that an alternate notation for Ckn is (n k) .

On this exercise, you will not key in your answer.
However, you can check to see if your answer is correct.