How To Calculate Combinations & Permutations

Suppose you have n types of items, and you wish to select a collection of r of them. We might want these items in some particular order. We call these sets of items permutations. If the order doesn't matter, we call the set of collections combinations. For both combinations and permutations, you can consider the case in which you choose some of the n types more than once, which is called 'with repetition', or the case in which you choose each type only once, which is called 'no repetition'. The goal is to be able to count the number of combinations or permutations possible in a given situation.

The factorial function is often used when calculating combinations and permutations. N! means N×(N–1)×...×2×1. For example, 5! = 5×4×3×2×1 = 120. The number of ways to order a set of items is a factorial. Take the three letters a, b and c. You have have three choices for the first letter, two for the second and only one for the third. In other words, a total of 3×2×1 = 6 orderings. In general, there are n! ways to order n items.

Suppose you have three rooms you are going to paint, and each one will be painted one of five colors: red (r), green (g), blue (b), yellow (y) or orange (o). You can choose each color as many times as you like. You have five colors to choose from for the first room, five for the second and five for the third. This gives a total of 5×5×5 = 125 possibilities. In general, the number of ways to pick a group of r items in a particular order from n repeatable choices is n^r.

Now suppose every room is going to be a different color. You can pick from five colors for the first room, four for the second and just three for the third. This gives 5×4×3 = 60, which just happens to be 5!/2!. In general, the number of independent ways to select r items in a particular order from n nonrepeatable choices is n!/(n–r)!.

Next, forget about which room is which color. Just pick three independent colors for the color scheme. The order doesn't matter here, so (red, green, blue) is the same as (red, blue, green). For any pick of three colors there are 3! ways you can order them. So you reduce the number of permutations by 3! to get 5!/(2!×3!) = 10. In general, you can choose a group of r items in any order from a selection of n nonrepeatable choices in n!/[(n–r)!×r!] ways.

Finally, you need to create a color scheme in which you can use any color as many times as you want. A clever bookkeeping code helps this counting task. Use three Xs to represent the rooms. Your list of colors is represented by 'rgbyo'. Mix the Xs into your color list, and associate each X with the first color to the left of it. For instance, rgXXbyXo means that the first room is green, the second is green and the third is yellow. An X must have at least one color to the left, so there are five available slots for the first X. Because the list now includes an X, there are six available slots for the second X and seven available slots for the third X. In all, there are 5×6×7 = 7!/4! ways to write the code. However, the order of the rooms is arbitrary, so there are really only 7!/(4!×3!) unique arrangements. In general, you can choose r items in any order from n repeatable choices in (n+r–1)!/[(n–1)!×r!] ways.