Introduction to Counting
From the very beginning of man, the questions of "How much?" and "How many?" have always demanded answers. Whether it be a shepherd wanting to know how many sheep have returned from pasture or an astronomer wanting to know how many galaxies exist in the universe we have often found a need to count things.
These and other counting problems range from the simple and mundane, to the more extreme and complicated. For example, it doesn't take much to count how many pennies you have in your piggy bank or even how many pieces of candy are in a particular jar; we would simply pull them out and count for each individual item. Not more complicated than that, but perhaps more time consuming, we could count and estimate how many blades of grass we have in our front lawn. More complicated problems begin to arise, however, when we start wanting to know how many ways we can create a unique meal from the items of a menu or how many outfits we can create given certain articles of clothing. No matter the difficulty, we need ways to answer these and other questions.
For more information on the history of counting, visit the History and Background page.
Back to TopAddition Principle
The easiest way to count is simply to add things up. However, we can't always just start adding. What do we do if you have repeated option? For example, let's say we are counting how many shirts we have, if we have two of the same shirt, do we count it twice or just once? To help establish a consistent way to add when counting we use the Addition Principle.
The Addition Principle
If a choice from Group \(N_{1}\) can be made in \(n_{1}\) ways, a choice from Group \(N_{2}\) can be made in \(n_{2}\) ways, and a choice from Group \(N_{i}\) can be made \(n_{i}\) ways, then the number of choices possible is \[n_{1} + n_{2} + \cdots + n_{i}.\]
Necessary Condition: No elements in any of the groups can be the same.
Adapted from: Illinois State University Mathematics Department
Example:
Let's suppose that after a student graduates from highshcool, she wants to work on an undergraduate degree in mathematics. She is considering four univerities in California, two universities in Utah, and three universities in Washington. The Addtion Principle tells us that she has \(4+2+3 = 9\) possiple mathematics undergraduate programs to choose from. (Adapted from: Chartrand and Zhang, 2011, p. 276)
Back to TopMultiplication Principle
Sometimes we want to make more than one choice. For example, let's say that Cox's Department Store has two positions to fill, those of a department manager and an assistant manager. Three people are eligible for the manager position, and four people are eligible for the assistant manager position (Rolf, 2005, p. 442). How many total choices do we have to fill both positions?
In order to answer this and other questions like it, we need to be introduced to the Multiplication Principle.
The Multiplication Principle
Two activities \(A_1\) and \(A_2\) can be performed in \(n_1\) and \(n_2\) different ways, respectively. The total number of ways in which \(A_1\) followed by \(A_2\) can be performed is \[n_{1} \times n_{2}.\]
(Rolf, 2005 p. 443)
For a proof, click here.
Example:
A taxpayers' association is to elect a chairman and a secretary. There are four candidates for chairman and five candidates for secretary. In how many different ways can a slate of officers be elected? (Rolf, 2005, p. 443)
Solution:
Since there are four candidates for chairman we have four choices. Then, for each one of the chairman, we have five choices for secratary. Thus, using the Multiplication Principle, we have \(4 \times 5 = 20 \) possible outcomes for a slate of officers.
Tree Diagrams
These type of problems are often easier to see and solve by using a tree diagram. For an in-depth look at tree diagrams, check out my Tree Diagram Applet.
Back to TopPermutations
A common application of the Multiplication Principle counts the ways a selection can be made from two or more sets such as the number of ways a person can select a salad, an entree, and a dessert from a menu (Rolf, 2005, p. 452). But what if we want to know the number of ways we can select a sequence of objects from the same set? That is where permutations come in.
To get an idea of how permutations work, consider how many ways five children be lined up? First we pick the first child out of the five. We have five choices. Then, we pick the second child out of the remaining four; four choices, then we have three for the next, then two, and finally one choice for the last child. Using the Multiplication Principle, we have \( 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \) possible choices to line up the children. Since this is a common enough operation, it gets its own notation. \( 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \).
There are a couple of caviats, however. First, we don't always want to use every element in the set. For example, perhaps we just wanted to pick three of the five children. Second, we may also want to be able to select the chosen elements again (we call this with replacement). If that is the case, then we have a different amount of possibilities. Thus we have the given definition of permutations.
Permutations
For a set of size \(n\) and a sample of size \(r\) , there are \(n^r\) different ordered samples with replacement and \(n(n - 1)(n - 2) \cdots (n - r + 1)\) different ordered samples without replacement.
The number of orderings of \(n\) elements is \(n(n - 1)(n - 2) \cdots 1 = n!\).
(Rice, 1995 p. 9)
For a derivation of a different formula, click here.
Example:
Ten students each submit one essay for competition. In how many ways can first, second, and third prizes be awarded? (Rolf, 2005, p. 453)
Soluton
This is a permutation problem without replacement (one essay can't win two prizes) with \( n = 10 \) and \( r = 3 \). So we get \( 10 \cdot 9 \cdot 8 = 720 \).
Back to TopCombinations
Like permutations, combinations deal with the ways we can take a sequence of objects from a set of objects. Unlike permutations, however, order doesn't matter. For example, consider how many different 5-card poker hands can be dealt from a 52-card deck. Here, the order we receive the cards doesn't matter. 4 aces and the jack of clubs is the same hand, no matter what order I received them. So here we have a combination problem.
Combinations
The number of unordered samples of \( r \) objects selected from \( n \) objects without replacement is \( \binom{n}{r} \). Where \[ \binom{n}{r} = \frac{n!}{(n-r)!r!}. \]
(Rice, 1995 p. 11-12)
To see and explore the relationship between combinations and permutations visit the Explanations Page and the Permuations and Combinations Applet.
Example:
A student has seven books on his desk. In how many different ways can he select a set of three? (Rolf, 2005, p. 466)
Solution:
Since order doesn't matter, we will use the combination formula with \( n = 7 \) and \( r = 3 \) and we get \( \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35 \).
Back to Top