13.09 Probabilities with permutations
Writing permutations
A permutation is a particular way that a group of objects could be selected and arranged. For example, If I have a red dot, blue dot and green dot; then I could choose any two of them and end up with the following options.
The idea of counting how many possible different combinations there are is part of a mathematical topic called Counting Techniques. For small sets like the one above, it's quite simple to write down all the choices and add them up. But for larger sets, we need a more efficient method of counting.
You'll notice that in the example above with the colored spots, a red and green spot is a different permutation to a green and red spot. We say that for a permutation, the order is important. That is, we call the red and green different to a green and a red.
Diagrammatic calculations
Using a diagram can help us work out the number of permutations a set of objects has.
For example, consider the set of letters $A,B,C,D$A,B,C,D and $E$E. We want to see how many different ways we can select and arrange a set of $3$3 letters.
A diagrammatic calculation starts with drawing boxes (or circles, or triangles, or any other shape you can write a number inside of), where the number of the boxes is equal to the number of objects we are selecting. In this case, we are selecting $3$3 letters each time, so we have $3$3 boxes.
Inside the first box, we write down how many possible choices we have for this box. We have $5$5 letters to choose from, so we have $5$5 options. Either $A,B,C,D$A,B,C,D or $E$E.
Inside the second box, we write down how many possible choices we have for this box. Because we had $5$5 to start with, we will have selected one already, so there are $4$4 options left for this next box.
Finally, inside the third box, how many possible letters will we have left to pick from? Only $3$3.
To calculate how many possible options we have we multiply these together.
So there are $60$60 possible permutations (or arrangements) for selecting $3$3 objects from the $5$5.
If there are $m$m ways for one event to occur and $n$n ways for a second event to occur, then there are $m\cdot n$m·n ways for both events to occur.
Worked examples
Question 1
There are $4$4 people who are lining up outside a store for an amazing annual sale. Fred, Ginger, William and Asteria. How many different arrangements are there for the four people in the line?
Think: We know that to fill the first position in the line we have $4$4 people to pick from. This leaves us with only $3$3 for the next position, and then $2$2 for the next and $1$1 for the last.
Do: This results in $4\times3\times2\times1=24$4×3×2×1=24.
Question 2
Determine the number of ways the letters of the word $HAPPY$HAPPY can be arranged in a line.
Think: There are $5$5 letters in the word $HAPPY$HAPPY. We want to keep in mind that the letter $P$P appears twice. This means that unlike arranging $5$5 unique letters, when we swap the letter $P$P with the other $P$P, we don't get a new arrangement.
Do: If $HAPPY$HAPPY was made up of $5$5 unique letters, then the result would be $5\times4\times3\times2\times1=120$5×4×3×2×1=120.
But this counts each permutation twice since it swaps position of the letter $P$P with the other $P$P. So we want to halve the resulting value.
| $\text{Number of arrangements }$Number of arrangements | $=$= | $\frac{120}{2}$1202 |
| $=$= | $60$60 |
Notation and formulas
Instead of writing out boxes or long products every time, we can use some helpful notation and formulas.
Factorial: The product of an integer and all of the natural numbers less than it. For an integer, $n$n, we say "$n$n factorial" and write $n!$n!.
Example: $5$5 factorial can be calculated as $5!=5\cdot4\cdot3\cdot2\cdot1=120$5!=5·4·3·2·1=120
When we were arranging $3$3 of the letters, $A,B,C,D$A,B,C,D and $E$E. We did the calculation $5\times4\times3$5×4×3. How could we write this using our factorial notation? Well $5!=5\times4\times3\times2\times1$5!=5×4×3×2×1, but we don't want the $2\times1$2×1. We can divide by $2\times1=2!$2×1=2! to cancel this out.
| $5\times4\times3$5×4×3 | $=$= | $\frac{5\times4\times3\times2\times1}{2\times1}$5×4×3×2×12×1 |
| $=$= | $\frac{5!}{2!}$5!2! |
Permutation formula: Once we are comfortable with the idea of arrangement, we can actually use a formula instead of the "boxes" or writing long products. Again, referring to the example with arranging $3$3 of the letters $A,B,C,D$A,B,C,D and $E$E, how could we jump right to $\frac{5!}{2!}$5!2!?
Well, we had $5$5 letters and were arranging $3$3. We can see the $5$5 in $\frac{5!}{2!}$5!2! in the numerator, the denominator is actually just $5-3$5−3.
For positive integers $n$n and $r$r, $n\ge r$n≥r, where $n$n is the total number of elements in the set and $r$r is the number to be ordered,
$_nP_r=\frac{n!}{(n-r)!}$nPr=n!(n−r)!
When there are duplicates, we can use this as a starting point and then divide to eliminate duplicates.
Cases
If there are different cases to consider, we will add up permutations of the distinct cases.
Worked example
Question 3
Suppose I have the digits $1,3,4,7,8,9$1,3,4,7,8,9. How many $3$3 digit odd numbers which are greater than $200$200 can be made?
Think: We have two cases here, one where the first number is odd in which can we lose one possibility for the last digit and one where the first number is even.
Do:
Case 1: The first number is odd.
For the first digit, it could be $3$3, $7$7 or $9$9. Now I don't have that choice for the last digit, but we do also have the choice of $1$1.
| $3$3 | $3$3 | |
|---|---|---|
| $3$3, $7$7 or $9$9 | $1$1 and two of $3$3, $7$7 or $9$9 |
After fulfilling these used $2$2 out of $6$6 numbers, so have $4$4 choices for the second number.
| $3$3 | $4$4 | $3$3 |
|---|
Case 2: The first number is even.
For the first digit, it could be $4$4 or $8$8. The last digit can be any of the odd numbers.
| $2$2 | $4$4 | |
|---|---|---|
| $4$4 or $8$8 | $1$1, $3$3, $7$7 or$9$9 |
After fulfilling these used $2$2 out of $6$6 numbers, so have $4$4 choices for the second number.
| $2$2 | $4$4 | $4$4 |
|---|
| Case 1 + Case 2 | $=$= | $3\times4\times3+2\times4\times4$3×4×3+2×4×4 |
| $=$= | $36+36$36+36 | |
| $=$= | $72$72 |
There are $72$72 possible numbers.
Practice questions
question 4
How many ways can $9$9 different items be arranged in a line?
QUESTION 5
At a gathering of political leaders, there are $3$3 delegates from European countries, $5$5 delegates from African countries, and $2$2 delegates from South American countries.
During question time, they are to be seated in a row on stage, however the South American delegates need to leave early and so are seated together to the right of the other delegates.
In how many ways can the delegates be seated?
QUESTION 6
In a certain code, the digits $0$0 and $1$1 are placed together to form a string and each string represents a word. For example, $11010$11010 is a string.
How many of these strings can be created using three $0$0s and four $1$1s?
Probabilities with permutations
We can also apply permutations to find the probability of an event. Let's consider the worked example below.
Worked example
Question 7
Suppose that $8$8 people enter a room and randomly stand in a line along the back wall. What is the probability that they stand from tallest to shortest, left to right?
Think: Recall that probability is defined as the following: $\frac{\text{number of desired outcomes}}{\text{number of total outcomes}}$number of desired outcomesnumber of total outcomes
To find the number of desired outcomes, we need to know how many ways people can line up from smallest to shortest. This is just $1$1 way.
To find the number of total outcomes, we need to find the total possible arrangements that $8$8 people can stand in a line. This can be evaluated with the factorial $8!$8!.
Do:
| $\frac{\text{number of desired outcomes}}{\text{number of total outcomes}}$number of desired outcomesnumber of total outcomes | $=$= | $\frac{1}{8!}$18! |
| $=$= | $\frac{1}{40320}$140320 | |
| $=$= | $0.00248%$0.00248% |
Reflect: Is the result what we'd expect?
Practice questions
QUESTION 8
The letters of the word SPACE are to be rearranged.
How many different arrangements are possible?
What is the probability that the letter E will be the first letter?
What is the probability that the letters are arranged in alphabetical order?
QUESTION 9
$8$8 cards have different letters written on them. The letters are $A,R,I,O,S,C,G,U$A,R,I,O,S,C,G,U. The cards are shuffled and laid out on a table with the letters face up next to one another.
How many possible arrangements are there?
What is the probability that the letters will spell the word GRACIOUS?