Permutations and Combinations

Some probabilityA measure of how likely it is that something will occur. situations involve multiple eventsA collection of possible outcomes, often describable using a common characteristic, such as rolling an even number with a die or picking a card from a specific suit.. When one of the events affects the others, they are called dependent eventsTwo or more events for which the occurrence of one affects the probability of the other(s).. For example, when items are chosen from a list or group and are not replaced, the first choice reduces the options available for later choices.

There are two possible ways to arrange or combine outcomesA result of a trial. of dependent events. PermutationsGroupings in which the order of members matters. are groupings in which the order of items matters. CombinationsGroupings in which the order of members does not matter. are groupings in which content matters but order does not.

Two events are dependent if the original state of the situation changes from one event to the other event, and this alters the probability of the second event.

So one way to tell whether events are dependent or independent is to find out whether a removed outcome is replaced (making them independent) or not replaced (making them dependent). Here are some examples:

Situation	Events	Why the events are dependent
At a party, you draw four names of the guests to form a team of four people. What’s the probability that John, Perna, Tosho, and Lee will be on a team together?	Draw John Draw Perna Draw Tosho Draw Lee	Once you draw a name, you don’t put that name back into the pool of names you draw from. Each time, there is one fewer name in the sample space, and (if the event continues to occur) one fewer name in the event space. The probability that the event happens changes with each new draw.
You pull a marble from a bag with `2` red marbles, `2` white marbles, and `1` green marble. You hold onto it and then pull another marble. What's the probability of pulling a red marble and then pulling the green marble?	First pull is red. Second pull is green.	The events are dependent because you don’t replace the first marble you pull. There is one fewer marble in the sample space, so the probability of picking a green one is different for the second pull than it was for the first pull.
You draw two cards from a standard deck of `52` cards. In a standard deck, each card has a suit (hearts, clubs, diamonds, or spades). Each card also has a rank (Ace, `2, 3, 4, 5,6, 7, 8, 9, 10`, Jack, Queen, or King). What is the probability that both cards are `2`'s?	One card is a `2`. The other card is a `2`.	Since two cards are drawn, the probability that the first is a `2` is different from the probability that the second is a `2`. (Fewer cards to choose from gives a smaller sample space.)

One thing we know about situations involving dependent events is that one action removes possible outcomes from future actions. There's another important issue to consider about the outcomes of dependent events: how are they organized? Must we make a list, noting the order in which they occurred, or do we just lump them together and ignore the order?

Consider the three examples given before, and think about whether order matters:

Situation	Events	Does the order matter?
At a party, you draw four names of the guests to form a team of four people. What’s the probability that John, Perna, Tosho, and Lee will be on a team together?	Draw John Draw Perna Draw Tosho Draw Lee	Order doesn’t matter. Those four people will be on the same team whether you draw John, Perna, Tosho, and then Lee, or Perna, Tosho, Lee, and finally John.
You pull a marble from a bag with `2` red marbles, `2` white marbles, and `1` green marble. You hold onto it and then pull another marble. What's the probability of pulling a red marble and then pulling the green marble?	First pull is red. Second pull is green.	Order matters. Pulling a green and then a red is not a successful outcome for this situation.
You draw two cards from a standard deck of `52` cards. In a standard deck, each card has a suit (hearts, clubs, diamonds, or spades). Each card also has a rank (Ace, `2,3,4,5,6,7,8,9,10`, Jack, Queen, or King). What’s the probability both cards are `2`'s?	One card is a `2`. The other card is a `2`.	Order does not matter. The outcome is satisfied whether you draw the `2` of hearts and then the `2` of clubs, or the `2` of clubs and then the `2` of hearts.

In situations that create groups of objects (such as people, marbles, or cards), we need to know whether their order matters or not. Otherwise we can't find the sample and event spaces accurately.

Consider the team example. In the sample space, the outcome John, Perna, Tosho, Lee is the same as the outcome Perna, Lee, John, Tosho—there is no difference between the teams created, even though the members are named in a different order. On the other hand, suppose the first person drawn had to be the one to toss a water balloon, the second had to be the one who caught it, the third had to be the one who pops it (if it’s still intact), and the fourth is the one who tries to catch the water in a cup! If John is a terrible balloon thrower but Perna is great at it, the better team order would be Perna, Lee, John, Tosho, so that Perna throws to Lee (who catches it), John (pops it), Tosho (catches the water). That would beat having the team order be John, Perna, Tosho, Lee, so that John throws to Perna (who catches it), Tosho (pops it), Lee (catches the water). Order matters.

Example

Problem

A bag contains `5` marbles, colored white, red, blue, purple and green. Find the size of the sample space if you pull two marbles, without replacement, in two ways: `1`) Order matters. `2`) Order does not matter.

First pull
W	R	B	P	G

List the possibilities for the first pull. To save space, just use the initials of the colors (since they’re all different).

		First Pull
		W	R	B	P	G
Second Pull	W		RW	BW	PW	GW
	R	WR		BR	PR	GR
	B	WB	RB		PB	GB
	P	WP	RP	BP		GP
	G	WG	RG	BG	PG

Sample space (order matters): {RW, BW, PW, GW, WR, BR, PR, GR, WB, RB, PB, GB, WP, RP, BP, GP, WG, RG, BG, PG}

Now add the second pull. Since we first want to look at when order matters, just add the second pull after the first one. Remember that this is without replacement, so you can’t repeat a color.

Sample space (order doesn’t matter): {RW, BW, PW, GW, BR, PR, GR, PB, GB, GP}

Now, how is this different when order doesn’t matter? WR and RW become the same outcome, as do WB and BW, and so on. In the diagram here, each outcome is paired with the equivalent outcome. Since you only need one of each pair, there are half as many outcomes.

Answer

When order matters, the sample space has `20` outcomes. When order doesn’t matter, the sample space has `10` outcomes.

When we make groups in which the order doesn’t matter, the groups are called combinations. When we make groups in which the order does matter, the groups are called permutations. Remember, with permutations, position (order) matters.

Since sample and event size are what we use to find probabilities, it’s helpful to know just how many combinations or permutations are possible. Here’s a way to think about it, using the Fundamental Counting Principal, which says that the number of outcomes in the sample space is the product of the number of outcomes for each element.

Let’s start with permutations, when order matters. Suppose we have `n` objects to choose from (`n` marbles in the bag, or `n` guests at the party, for example).

See where this is going? Notice that the last factor subtracts one less than the total number of objects chosen. To find the number of options for choosing the `k`th object, multiply the previous outcomes by `n-(k-1)`. Another way to write `n-(k-1)` is `n-k + 1`.

For combinations, order doesn’t matter. How does that change the number of outcomes? The number of permutations that become the same when order no longer matters is the number of ways to arrange the objects in a group.

Think about a group of three letters, A B C. In a permutation situation, A B C and C A B are different outcomes, but in a combination situation, these outcomes are the same. How many different ways can the letters A, B, and C be arranged? That is, how many permutations are there for this one particular group?

There are `6` ways to arrange the letters. Notice that what we’re doing is finding the number of permutations of `3` objects when we choose all `3` (`n=3` and `k=3`). So, using the formula provided above, there are `3*2*1 = 6` outcomes. This matches the list of actual outcomes.

In the marble example, we had `2` objects in each group, so for each pair of marbles, there were `2*1`, or `2`, ways to arrange them. We only needed one from each pair, so the number of combinations was the number of permutations divided by `2`. In the letter example, since there are `6` ways to arrange three objects, when we’re finding combinations of three we only need one representative from those `6` ways. We can divide the number of permutations by `6` to get the number of combinations.

This is true in general: to find the number of combinations of `k` objects taken from `n` objects, divide the number of permutations for choosing `k` of `n` objects by the number of permutations for choosing `k` of `k` objects.

There’s an easier way to write permutation and combination formulas, using an idea called factorialsAn abbreviated way of writing a product of all whole numbers from `1` to a given number, indicated by that number followed by an exclamation point, as in `3!` = `3 * 2 * 1`.. A factorial is a product of all the whole numbers from `1` to a given number. The exclamation mark symbol (!) after a number is used to represent this product. For example, `3! =3*2*1`, and `7! = 7*6*5*4*3*2*1`. So, in general, `n! = n*(n-1)*` ... `*2*1` Special note: `0!` is defined to be `1`.

The number of permutations formula starts out like `n!`, but it ends with `(n-k + 1)` instead of `1`. We need to remove the factors from `(n-k)` to `1` from the product. We can do that by dividing by `(n-k)!`.

`n(n-1)(n-2)...(n-k+1)=(n(n-1)(n-2)...(n-k+1)(n-k)(n-k-1)...(2)(1))/((n-k)(n-k-1)...(2)(1))=(n!)/((n-k)!)`

Many calculators have a factorial (!) key or command. To find the number of permutations of choosing `20` of `24` objects, entering `24!-:4!` is a lot faster and easier than `24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5`. (Then again, if only `4` choices are made, it may still be easier to enter `24*23*22*21`.)

Let's try these formulas on a problem. First, we'll use the Fundamental Counting PrincipleA way to find the number of outcomes in a sample space by finding the product of the number of outcomes for each element..

Example
Problem	A school organization has `30` members. Four members will be chosen at random for an interview with the school newspaper about the group. How many groups of four are possible?
	combination	First, decide if this is a permutation or a combination situation. There’s no reason for any person to be considered different from any other, based on the order chosen, so this is a combination.
	`302928*27`	There are `30` possibilities for the first pick. Then `29` possibilities for the second person, `28` for the third, and `27` for the fourth. The Fundamental Counting Principle says we multiply these outcomes to get the total number of possibilities.
	`(30292827)/(4321)`	However, that product gives us the number of permutations, when order matters. We need to take all the arrangements of four particular people and use just one representative of each. For four people, there are `4` choices for the first to be listed, `3` choices for the second, `2` for the third, and then only `1` choice for the last in the list. The Fundamental Counting Principle again tells us how many times a group of `4` people will show up in the permutations list. Divide by the product provided by the Fundamental Counting Principle.
Answer	There are `27,405` different groups of `4` people possible from the `30` members!

Example
Problem	A school organization has `30` members. Four members will be chosen at random for an interview with the school newspaper about the group. How many groups of four are possible?
	combination	First, decide if this is a permutation or a combination situation. There’s no reason for any person to be considered different from any other, based on the order chosen, so this is a combination.
	`(30!)/((30-4)!4!)` `(3029282726...21)/((26...21)(4321))` `(26...21)/(26...21)(30292827)/(4321)` `1(30292827)/(432*1)` `27,405`	The factorial formula for combinations is `(n!)/((n-k)!k!)`. In this case, we’re choosing `4` of `30` members, so `n = 30` and `k=4`.
Answer	There are `27,405` different groups of `4` people possible from the `30` members!

Two (or more) events are dependent if the probability for one event changes when the success of the other event is determined. This typically happens when the random action for one event removes a possible outcome and the outcome is not replaced before the action for the other event happens.

To find the sample and event spaces for these situations, consider whether the events involve permutations (order matters) or combinations (order does not matter). There are two ways to calculate sample and event space without listing them all and counting, with the Fundamental Counting Principle and with factorial formulas.

The Fundamental Counting Principle allows us to find the number of permutations and combinations as follows:

When choosing `k` of `n` objects, the number of permutations is: `n(n-1)(n-2)...` `(n-k+1)`

When choosing `k` of `n` objects, the number of combinations is: `(n(n-1)(n-2)...(n-k+1))/(k(k-1)...(2)(1))`

Learning Objective

Introduction

Dependent Events

Permutations and Combinations

Sample Size and the Fundamental Counting Principle

Sample Size and Factorials

Summary