Introduction to Counting

In this introduction to counting we'll start to learn about the words product rule, perumutation, combination, as well as how to count permutations and combinations.

Product Rule

On a standard die, there are six sides. If we were to roll this die twice, there are possible outcomes. For each value of the first roll, there are six values for the second roll. Since the first roll also has six options, we derive the total number of possible outcomes as . This is a specific example of the more general product rule.

Product rule. Suppose you have a set of sequences of elements and that there are possible choices for the first element in a sequence. Suppose further that for the second element of a sequence there are possible choices, possible choices for the third element, and so on, until the th element where there are possible choices. For sequences of elements, there are possible sequences in the set.

Example. Suppose you are going to assemble a computer. If there are two CPU companies to choose from, four hard drive companies, three memory companies, and accesories from five brands to choose from, how may different computers could you configure?

There are CPU companies to choose from, hence . Further, . You could therefore make different computers.

Permutation

Permuation. An ordered sequence of elements is called a permutation.

For a permutation, the order of the elements in the sequence is part of the definition of the sequence. For instance, two permutations are considered different even if they contain the same set of numbers, so long as the numbers appear in the sequence in a different order.

Example. is a permutation of the set of numbers . The permutation is a different permutation than the first. Example. Zip codes are permutations, because the order of the numbers defines different zip codes. The zip code is different from since the digits show up in a different order.

Combination

Combination. An unordered sequence of elements is called a combination.

You might hear the phrase a sequence where "order does not matter." I've always found this phrase less than helpful. What is meant is that so long as the sequence contains the same numbers, the two sequences hold the same meaning; two sequences with the same set of numbers are effectively the same combination.

Example. is a combination of the set of numbers . The combination would be considered the same combination as the first.

Example. In five card poker, from a standard deck of cards, a full house consists of two of the same card and three of another. For instance, the hand 2 of hearts, 2 of spades, 3 of clubs, 3 of diamonds, and 3 of hearts is called a full house. The hand 2 of spades, 2 of hearts, 3 of clubs, 3 of diamonds, and 3 of hearts is still a full house.

Counting Permutations and Combinations

Counting invariably involves determining the number of permutations and/or combinations associated with various events.

Example. Suppose that a college of engineering has seven departments, which are denoted by . If each department has one representative in the college, how many ways are there to select a chair, a vice-chair, and a secretary to the college board? Since the board fills the roles differently than the board , these are permutations of the department representatives.

Using the product rule we have ways to choose the chair, ways to choose the vice-chair, and ways to choose the secretary, assuming that no representative can hold more than one position. Hence, there are ways to choose a board.

The number of permutations can be written mathematically as . From the example above, we have .

Example. Consider again the college board example from above. Suppose now that only three representatives will be selected, but that they are no longer assigned to roles. Three will be selected and all that matters is which three are selected. How many combinations of representatives can be selected to the college board?

Consider the combination . These three individuals can be ordered in ways to produce the permutations . There are ways to order any combination of representatives. There are therefore combinations of representatives that could be selected for the college board.

This implies the following relationship between the number of combinations and the number of permutations. The number of combinations is written as . Notice then that there are more permutations than combinations. There is more permutations than combinations, because is the number of ways each combination can be ordered.

We thus define the operation named choose as

, which we read as choose .