In general, the branch of mathematics that deals with questions of the form: "How many ways is it possible to arrange a certain set of objects, given a certain set of conditions."
Statement 1. If you have several different choices to make, then the total number of ways that you can make all of the choices, is the product of the number of ways that you can make each individual choice.
Example: If you have 5 pairs of pants, and 7 sweaters, and 3 hats, the total number of different outfits you can assemble consisting of a hat, sweater and pants is 5 x 7 x 3 = 105.
Statement 2. If you have N different objects, then the number of different ways you can arrange them in order, is N x (N-1) x (N-2) x ... x 3 x 2 x 1, or N! , or "N factorial".
Example: The number of different ways you can arrange the three letters ABC in order, is 3 x 2 x 1 = 6. (They are: ABC, ACB, BAC, BCA, CAB, CBA.) The number of different ways you can arrange the letters ABCD is 4 x 3 x 2 x 1 = 24.
This actually follows from Statement 1, because when you are arranging N different letters in a row, you have N choices for what letter to put in the first position, then you have N-1 choices for what letter to put in the second position (now that the first letter you chose is no longer available), and so on, all the way until you have 1 letter left to put into the last position. So from statement 1, the total number of ways that you can make all of those choices, is N! , or N x (N-1) x (N-2) x ... x 3 x 2 x 1.
Suppose you want to count all the ways that the letters in the word "ARMADA" can be arranged. Note that the answer is not 6!, given by Statement 2 above, because Statement 2 only says that 6! is the number of ways that 6 different objects can be arranged, and "ARMADA" contains three of the same letter, A.
The trick is to first pretend that the three A's are different letters (call them A1, A2, and A3), and count up how many ways the letters in the word can be arranged. That will give you an answer that is too large, because when you're counting the A's as different letters, you end up counting certain arrangements more than once, for example:
As long as we're pretending that the A's are "different letters", then these look like different arrangements, but of course if the A's are counted as the same letter, then these are just versions of the same arrangement, MRAADA. So to get the true answer, we have to determine how many duplicates are in the list, and eliminate those.
First, we know that if A1, A2, and A3 are counted as different letters, then by Statement 2 we know that the letters can be arranged in 6! different ways. But then how many times has each "true arrangement", such as MRAADA, been overcounted in this list? The sequence MRAADA appears 6 different times:
And it appears exactly 6 times because the number of ways that you can arrange A1, A2 and A3 to fill those three positions, is given by Statement 2, as 3! = 3 x 2 x 1 = 6.
By the same reasoning, in our list of words where we counted A1, A2 and A3 as different letters, every arrangement of the letters in the word "ARMADA" shows up 3! times. So to get the true answer, we have to take the total number of arrangements in the list, "6!", and divide by "3!". The answer is that the number of ways you can arrange the letters in the word "ARMADA" is 6!/3! = 120.
This is an example of one general strategy for solving combinatorics problems:
Example: if you are arranging 5 people A, B, C, D, and E around a circular table, how many different ways can they be seated, assuming that only their order around the table matters, not the actual chairs that people are sitting in? (In other words, if everybody gets up and moves one seat to the left, that is still considered the "same arrangement", not a different one.)
The use of the words "same" and "different" in the question hopefully triggered some thoughts about using Strategy 1. We said that only the order around the table matters, so the following five arrangements are considered the same:
|is the same as:|
Suppose you want to arrange 7 people, A, B, C, D, E, F, and G in seats at a movie theater. But A, B, and C have been best friends since first grade and insist on sitting together (although not necessarily in the order ABC). How many ways can they be seated?
The trick is to first think of the group ABC as a single person, and figure out how many arrangements are possible under that assumption. If you think of the group ABC as a single wad of human flesh with cell phones, then instead of arranging 7 people in order, you're now arranging 5 people in order, and the number of ways to do that is 5! , or 120.
Except, that number doesn't take into account the number of different ways that the ABC-group can arrange themselves within their own group. For each arrangement in our original list, such as:
G F D [ABC-group] E
there are actually 6 possible arrangements:
G F D A B C E
G F D A C B E
G F D B A C E
G F D B C A E
G F D C A B E
G F D C B A E
because the number of ways that the 3-member group ABC can be arranged, of course, is 3! , or 6. So to get the true number of possible arrangements, we have to take our intermediate answer of 5! and multiply by 3! , and the answer is 5! x 3! = 120 x 6 = 720.
This suggests another strategy for solving combinatorics problems, which is the inverse of Strategy 1:
Suppose you want to arrange A, B, C, D, E in seats at a movie theater, except that A refuses to sit next to B (she knows what she did). How many ways can the people be seated?
It's easier to calculate the total number of ways that the people can be seated, and then subtract all the arrangements where A and B are sitting next to each other. We know that there are 5! = 120 ways in which the 5 people can be seated. Using a strategy similar to the last problem, we know that there are 4! x 2! = 48 arrangements in which A is sitting next to B. This leaves 120 - 48 = 72 arrangements in which A and B are not sitting next to each other.
Before looking at an example with rules involving overlapping groups, we should look at an example with rules involving non-overlapping groups, to show why those are easier.
Suppose you want to arrange 7 people, A, B, C, D, E, F, and G, in seats at a movie theater, subject to the rules:
Using Strategy 2, we consider the ABC-group to be a single clump, and the EF-group to be a single clump. Now we're arranging 4 clumps: ABC-group, EF-group, D, and G, and the number of ways they can be arranged is 4!. For each of those arrangements, we have 3! choices as to how we arrange A, B, and C within their group, and we also have 2! choices as to how we arrange E and F within their group. So, going back to Statement 1, the total number of possible arrangements is 4!3!2! = 288.
But now, make a small change: You want to arrange A through G in their seats such that:
It is no longer possible to use a simple application of Strategy 2, because you can't clump A, B, and C together into one clump, and C and D into another clump.
There is no master strategy that will help you solve all problems of this kind. But as a general rule, you should look for nested groups rather than overlapping groups as an intermediate step to solving the problem.
For example: first consider all the ways that the people can be arranged with A, B, and C sitting next to each other. Using Strategy 2, the number of arrangements is 5!3! = 120 x 6 = 720.
Now instead of asking how many of those arrangements have D sitting next to C, ask how many of those arrangements have D sitting next to the ABC-group. If we still consider the ABC-group to be a single clump, then we have a group of 5 "objects" to sort: ABC-group, D, E, F, and G. How many ways can they be arranged with D next to the ABC-group? We use Strategy 2 again, grouping the ABC-group and D into a larger group, call it the ABC-D-group.
Now we have 4 "objects" to sort: ABC-D-group, E, F, and G, so they can be arranged in 4! ways. For each of those arrangements, within the ABC-D-group, the two sub-clumps -- the ABC-group and the element D -- can be ordered in 2! ways. And finally, within the ABC-group itself, its members can be ordered in 3! ways. So the number of arrangements such that:
Except that's not what we originally asked. Of the 720 arrangements that have A, B, and C sitting together, we didn't ask how many had D sitting next to the ABC-group, we asked how many had D sitting next to C.
Fortunately, there's an easy route from here to the answer. In all the arrangements that have D sitting next to the ABC-group, D is only sitting next to one member of that group. Since there are 3 possibilities for which member that will be, exactly 1/3 of the time D is sitting next to C. So if there are 288 arrangements where D is sitting next to the ABC-group, the number where D is sitting next to C is 288/3 = 96.
This suggests a general approach that we can call Strategy 4, which we can use when the problem gives conditions on overlapping groups:
The number of ways that you can choose M objects from a set of N objects, if it doesn't matter in what order the M objects are chosen, is given by the well-known formula for "N-choose-M":
|or "N choose M" is given by:||
(Note: you never call this "N over M". "N over M" refers to the fraction, which is different from N-choose-M.)
This formula actually follows from Statement 3, because the question of "How many ways can you choose
M objects from a set of N objects, if order doesn't matter?" is the same as the question of "How many
ways can you arrange a group of N letters, if M of them are A's and the rest are B's?":
(Choosing which of the N positions will be filled with A's, is the same as choosing which objects from a group of N objects will be selected.)
The following are special cases of the formula N-choose-M. The second column shows the value that you would get by substituting numbers into the N-choose-M formula; the third column explains why this number is what you'd expect to get:
|Special case||Result given by the formula||Reason why this result makes sense|
|1||There is only 1 way to choose 0 objects from N objects -- don't choose any of them.|
|N||There are exactly N ways to choose 1 object from N objects -- one way for each object.|
|1||There is only 1 way to choose N objects from N objects, because there are N objects to choose from.|
|The reason that the two values are equal, is that every way of choosing M objects from a group of N, corresponds to a way of choosing N-M objects from that group of N -- because instead of choosing the ones that you did select, instead choose the ones that you didn't select.|
Suppose you have 10 identical tennis balls and you want to sort them into 5 bins labeled 1 through 5. Each bin may contain 0 balls or it may contain up to all 10 of them. How many different ways can this be done? (Note: the word "bin" is usually only used in British English to mean "container", however it's still used by American mathematicians when talking about combinatorics problems.)
This would appear to be unrelated to any of the previously discussed problems, but it's
actually very similar to the problem of arranging groups of identical objects. Instead
of concentrating on the 10 tennis balls and 5 bins:
concentrate on the 10 tennis balls and the 4 boundaries between the bins:
The problem of sorting the tennis balls into the bins now just becomes the problem of arranging the tennis balls and the boundaries into a certain order. For example, this sorting of the tennis balls into the bins:
corresponds to this sorting of 10 instances of the letter T and 4 instances of the letter B:
SO the question reduces to: How many ways can you arrange, in order, a group of 10 identical objects and 4 identical objects? And we know the answer to that is:
How many unique ways can you arrange the letters in the word EMBEDDED?
Suppose you have 5 beads: 1 yellow, 1 red, 1 blue, and 2 green, and you want to arrange them on a necklace. (Remember that the necklace can be rotated, so for example the order YRBGG is the same as the order BGGYR, and the necklace can also be flipped over, so the order YRBGG is the same as the order GGBRY.) How many unique ways can the beads be arranged on the necklace?
If you have five friends A, B, C, D, E sitting in a row at a movie theater, how many ways can they be seated so that B is not sitting immediately to the right of C?
If you have the same five friends A, B, C, D, E sitting in a row, how many ways can they be seated so that B is sitting anywhere to the right of C (not necessarily next to C)? (Hint: Consider all the possible arrangements. For every arrangement with B sitting to the right of C, there is an opposite arrangement with B sitting to the left of C...)
You are sorting assigning 6 people, A, B, C, D, E and F, into 3 different hotel rooms. How many ways can they be sorted such that A is in the same room with C, and B is not in the same room with D? (Some hotel rooms may be empty.)
Again, you are sorting A, B, C, D, E and F into 3 different hotel rooms. How many ways can they be sorted such that A is in the same room with B, but B is not in the same room with C?