Combinatorics

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."

Review (should know already)

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.

Strategies for solving combinatorics problems

Strategy 1: pretend that arrangements which are "the same" are really different

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 A₁, A₂, and A₃), 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:

MRA₁A₃DA₂
MRA₃A₂DA₁

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 A₁, A₂, and A₃ 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:

MRA₁A₂DA₃
MRA₁A₃DA₂
MRA₂A₁DA₃
MRA₂A₃DA₁
MRA₃A₁DA₂
MRA₃A₂DA₁

And it appears exactly 6 times because the number of ways that you can arrange A₁, A₂ and A₃ 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 A₁, A₂ and A₃ 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:

Applying Strategy 1, we first pretend that the five arrangements shown above really are counted as "different" from each other. Now the question is just to list all the possible ways that a group of five people can be seated in five fixed chairs, and Statement 2 tells us that the answer is "5!".

Now, figure out how many times each true answer is over-counted. In our list above, where we counted every possible seating arrangement as "different" even if the order around the table is the same, each truly "unique" arrangement was counted 5 times. So get the true answer we divide 5! by 5 to get 24, which is the number of unique ways that 5 people can be seated around a circular table.

(There is another way of getting the same answer. Since we don't care which chairs the people actually sit in, we only care about their position relative to each other, for every unique arrangement you could just assume that person A was always sitting in the same chair. Once person A has picked their chair, then you do care about which chairs the other 4 people sit in, and then the problem becomes one of finding how many ways the other 4 people could sit in their 4 chairs relative to person A. Statement 2 says that the answer is 4! or 24.)

Repeated application of strategy 1

If you're counting arrangements of letters in a word like BELLEVUE, which has more than one group of identical letters (two L's and three E's), then you can apply strategy 1 multiple times.

First, pretend that all the letters (including all the L's and all the E's) are different. If that were true, and you made a list of all the ways that the 8 letters in the word could be arranged, you would have 8! = 40320 ways.

Now remove the assumption that the two L's are "different letters", and you find that each entry now appears twice in your list, so you divide the total number of entries in the list by 2!. Then remove the assumption that the E's are "different letters", and again you find that each arrangement is now repeated 3! times, or 6 times, in the list, so to get the number of truly unique entries you must divide by 3!. So the true number of possible arrangements of the letters is: 8!/(2!3!) = 3360.

Statement 3: In general, if you have a set of M objects, and it contains one subset of size N₁ of identical objects, and another subset of size N₂ of identical objects, and so on up to N_i, then the number of unique ways to arrange the objects in order, is given by repeated application of Strategy 1:

M!

N1!N2!...Ni!

Strategy 2: pretend that arrangements which are "different" are really the same

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:

1. Pretend that arrangements in the problem that are different, are really "the same".
2. Calculate the number of possible arrangements under those conditions.
3. "Stop pretending" -- i.e., remembering that arrangements that you counted as "the same" are really different. Then figure out how many times each "true arrangement" was under-counted in your answer in step #2. Thus the answer in step #2 must be multiplied by that amount to arrive at the true answer.

Strategy 3: Instead of counting arrangements that meet condition X, count up arrangements that do not meet condition X, and subtract

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.

Strategy 4: Rules that involve overlapping groups

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:

1. A, B, and C must sit together
2. E and F must sit together

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:

1. A, B, and C must sit together
2. C and D must sit together

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:

1. A, B, and C are sitting next to each other
2. D is sitting next to the ABC-group

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 = 36.

This suggests a general approach that we can call Strategy 4, which we can use when the problem gives conditions on overlapping groups:

1. Pretend that one of the conditions on the second group, instead of relating to just a subset of elements in the first group, relates to the entire first group. (e.g. instead of "D must sit next to C", have "D must sit next to the ABC-group".)
2. Calculate the number of possible arrangements under those conditions.
3. "Stop pretending" -- i.e., remembering that the condition that involves the second group really only involves a subset of the first group. Then determine what fraction of your arrangements meet the true condition. (e.g. of all the arrangements with D sitting next to the ABC-group, only 1/3 have D actually sitting next to C.)

Results obtained using these strategies

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":

(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?":
     AABBBABABBAAAAA
(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.)

Special cases of N-choose-M

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:

Sorting into bins

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:
    TTTBTTBTTBTTTB
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:

(	14	)
	10

Practice problems

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?