Permutations, Combinations Flashcards
Formual for Indistinguishable Elements
In this case, the number of permutations of {A, A, B, C} will be:
Why is this so? Basically, every permutation of {A, A, B, C} has two “versions”: A1A2BC and A2A1BC, to take just one example. There isn’t really a perceptible difference between them, since switching the two A’s doesn’t make the permutations look any different. Dividing the factorial of the total number of elements by the factorial of the number of indistinguishable elements eliminates the duplicated permutations.
What is an example of a permutations question with distinguishable elelments (e.g., {A, B, C, D})?
So we have 5 “positions” and 6 people to fill them. We first need to determine how many people can fill the first role/position. Since there are 6 people who could play the part, there are 6 people available.
Then how many performers would be available to play the second role cast? Since one performer has already been cast, there are only 5 performers still available.
Now we are seeing a pattern emerge, and it will continue until all the roles have been filled. So we end up with 6 available for the first, then 5, 4, 3 and finally 2. What do we do with these? We multiply them. So we end up with 6 × 5 × 4 × 3 × 2 = 720.
If, for example, we’d been asked to find the number of possible arrangements of 8 people in 4 positions, we would’ve ended up with 8 × 7 × 6 × 5 = 1680. 7 people in 3 positions would’ve given us 7 × 6 × 5 = 210.
What is the difference between combinations and permutations?
Permutations are concerned with the ordering of a single group, whereas combinations are concerned only with the composition of subgroups without regard to their sequence. In other words, in permutations order matters, but in combinations it doesn’t.
For example, let’s take the set {A, B, C, D, E}. If we wanted to form distinct subgroups of 3 elements each, we could have ABC, ABD, ABE, etc. These are all different combinations, since no two contain all the same elements. ABC and BCA, though, are different permutations of the same combination because they contain exactly the same elements.
What is the formula for combinations?
Order does not matter
In this formula, the variables represent the following:
n = the total number
k = elements we want in each subgroup
What do you do if the factorials are getting too large? The shortcut
On your scrap paper, draw out a dash for each of the elements in the subgroup. In this case, we have 2 elements in the subgroup, so we draw out 2 dashes.
Above the first dash write the total number you’re choosing from. In this case it will be 20.
Now over the remaining dashes count down from the first number until you run out of dashes. In this case, we’d put a 19 over the second dash.
Under the first dash write the number you’re choosing. In this case, we’d write a 2. Now under the remaining dashes, count down from the first number until you run out of dashes. In this case, we’d put a 1 under the second dash
