Combinations and Permutations

The product principle gives us a way to count the number of outcomes when each outcome is made by combining smaller pieces. A typical example of this is to count the number of three-letter words; each outcome (word) we count is made up of a combination of three smaller pieces (letters). Since there are 26 choices for each smaller piece, there are \(26\cdot 26\cdot 26 = 26^3\) possible outcomes.

The product principle does not require that each piece that is being combined be chosen from a set of the same size. We will use this observation to create a standard way to count outcomes when the pieces are chosen from a fixed set, but without allowing for any piece to be used more than once. For example, we can ask how many 3-letter words there are that contain distinct letters.

These arrangements are called permutations. We will also consider another counting technique where we count combinations, which is related but counts something different. We will explore how these two counting techniques are related and how they can be used to solve a wide range of counting problems.

A permutation is a (possible) rearrangement of objects. For example, there are 6 permutations of the letters a, b, c: \[abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba\]. In terms of our discrete structures, each permutation is really a sequence or tuple of a fixed length.

We know that we have them all listed above there are 3 choices for which letter we put first, then 2 choices for which letter comes next, which leaves only 1 choice for the last letter. The multiplicative principle says we multiply \(3\cdot 2 \cdot 1\).

A piece of notation is helpful here: \(n!\), read \(n\) factorial, is the product of all positive integers less than or equal to \(n\) (for reasons of convenience, we also define 0! to be 1). So the number of permutations of 6 letters, as seen in the previous example is \(6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\). This generalizes:

Sometimes we do not want to permute all of the letters/numbers/elements we are given.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Let's consider another way to count sequences: First count sets, then arrange them.

The example above illustrates a second way to compute the number of \(k\)-permutations of \(n\) elements: First select which \(k\) elements will be in the permutation, then count how many ways there are to arrange them. Once you have selected the set of \(k\) objects, we know there are \(k!\) ways to arrange (permute) them. But how do you select \(k\) objects from the \(n\)? You have \(n\) objects, and you need to choose \(k\) of them. You can do that in \(\binom{n}{k}\) ways.

Using the multiplicative principle to combine the two steps, we get another formula for \(P(n,k)\): \[P(n,k) = \binom{n }{ k}\cdot k!\].

This is HUGE!

We have a closed formula for \(P(n,k)\) already. We can substitute that in: \[\frac{n!}{(n-k)!} = \binom{n}{k} \cdot k!\].

If we then divide both sides by \(k!\), we get a closed formula for \(\binom{n}{k}\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We have two ways to write the numerical relationship between the numbers of combinations and permutations. Using the product principle, we have, \[P(n,k) = \binom{n}{k} \cdot k!\] which can be rewritten as, \[\binom{n}{k} = \frac{P(n,k)}{k!}\]. This second formula suggests that there might be a quotient principle that we could use to justify it.

Let's think about what division means. One way to think of the division problem \(24 \div 6 = 4\), for example, is saying that if you have 24 things that you divide into groups of size 6, the number of groups will be 4.The other way to interpret this statement is that if you divide 24 things into six groups, then each group will have size 4, but this is less useful for what we will do.

Now let's look at all the 3-permutations of a set of size 4: For example, all the ways to make 3-letter words using the letters \(a, b, c, d\). We know the number of such words is \(P(4,3) = 4\cdot 3 \cdot 2 = 24\). It is helpful to actually list all these out.

Look at the first row. What do all these permutations have in common? These are exactly the permutations that use the letters \(a, b, c\) in different orders. It is not surprising that there are 6 of these, since the number of ways to arrange three elements is \(3! = 6\). Similarly, the second row has 6 permutations that use the letters \(a, b, d\) in different orders, and so on.

The point is, if we wanted to just count how many sets of three of the four letters we have, each set corresponds exactly to one of the rows in the table. There are 24 elements in the table, and 6 elements in each row, so there must be \(24 \div 6 = 4\) rows. And of course, we are not surprised because \(\binom{4}{3} = 4\).

A more mathematically rigorous explanation for this phenomenon is to use the language of equivalence relations and partitions from . We start with permutations, and then we define an equivalence relation on the permutations by saying two permutations are equivalent provided they contain exactly the same elements. From the equivalence relation we get a partition of our set of permutations into equivalence classes. The combinations we want to count are precisely the equivalence classes. Since each equivalence class has the same size, we can find the number of classes by dividing the number of permutations by the size of each class.

This sort of quotient principle is also useful for solving questions where the answer isn't obviously either a permutation or combination.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.