Basic Counting Principle

Consider r experiments, where the i experiment has n_i possible outcomes. The basic counting principle tells us that the total number of (joint) outcomes for each of the r experiments is given by

$$n_1 \cdot n_2 \cdot \cdots \cdot n_r$$

Permutations

Permutations are sequences of elements where order matters. Permutations help with the general problem where we want to count the number of ways elements can be arranged where order matters. For example, if we have 8 contestants competing for a gold, silver, and bronze medals, how many different ways can I award the 3 medals among the 8 contestants? Here order matters: if I gave gold to Alice, silver to Bob, and bronze to Charlie, that’s specifically different than if I had given gold to Bob, silver to Charlie, and bronze to Alice, even though the recipients are still the same. To count the number of ways we can assign the 3 medals among the 8 contestants, we use the permutation formula

$$P(n,k) = \frac{n!}{(n-k)!}$$

Intuitively, we begin by counting the number of ways to give 8 medals to 8 contestants (8!), and then divide out the 5 medals we don’t really give out (5!), leaving us with only the first 3 pieces of the 8!. Overall, our formula P(n,k) tells us the number of ways to arrange any set of k elements chosen from all n elements. In other words, it gives the number of distinct (ordered) k-tuples that can be created from the set of n elements (without repetition).

Special Cases (?)

• Counting permutations of n elements: using the equation given above, we can see this is just n!. It’s a simple application of the multiplication principle, where selecting elements for an ordered arrangement can be thought of as a series of events. The first has n possible outcomes, the second n-1, the third n-2, and so on. Since we’re considering the total number of joint outcomes, we multiply the number of outcomes together and arrive at n!.

• When some elements are indistinguishable: we must take extra care not to double count arrangements that appear exactly the same. Suppose we have n elements, and among these elements there are r groups of indistinguishable elements. We denote the number of elements in each of these groups as

  $$n_1, n_2, \dots, n_r$$

  We can find the number of distinct permutations by first considering each of the n elements to be unique, count the number of permutations, and then divide through by the number of repeated arrangements. For each group of n_i similar elements, there are n_i! ways to arrange them within a given arrangement (without changing how that arrangement appears). So the total number of distinct permutations in this case is given by

  $$\frac{n!}{n_1! \cdots n_r!}$$

• Alternate interpretation of permutation formula: one can relate the permutation formula to the indistinguishable example. n! gives the total number of n-permutations, and for each of these permutations there are n-k elements we don’t care about (since we only choose k elements). In each k-permutation, n! counts these n-k elements (n-k)! times, and so we divide these repetitions out to get the total number of k-permutations we can choose from n elements.

Combinations

Combinations are groups of elements where order doesn’t matter. Using a modified version of the medal example from above, we now consider picking the top 3 winners from the 8 contestants. Here order doesn’t matter; choosing Alice, Bob, and Charlie is the same as choosing the Bob, Charlie, and Alice. In this instance they are a group, and so long as the group contains the same elements, they are considered the same combination. To construct the formula for counting the number of combinations there are of k items chosen from a set of n items, we can start with the permutation formula:

$$\frac{P(n,k)}{P(k,k)} = \frac{n!}{(n-k)!k!} = {n \choose k}$$

Here we simply count the number of permutations of size k that can be made, then divide out by the number of ways a given group of the same items could be arranged. This follows a similar line of reasoning as the indistinguishable elements case above: we treat each of the k elements as “indistinguishable” in the sense that the elements are viewed exactly the same in any other order. Thus, different permutations of the same elements are only counted once, acting like a combination. For our example, we would take the unique number of ordered ways to choose the top 3 (ie P(8,3)) and divide by 6 (ie 3!), the number of permutations that contain the same group of 3 individuals, just in different orders. Our formula gives the number of k-combinations from a set S of n elements.