Unit 2: Counting Theory
"How many elements do we expect to find within a given set?" This is a simple question, but hard to answer correctly without guessing. Counting theory (also known as combinatorics) lets us do that through several different approaches that depend on the circumstances of the given problem. These approaches are not difficult, but you have to know when to use each one, and which circumstances each approach applies to. In this unit, we will carefully walk through these considerations.
Completing this unit should take you approximately 5 hours.
Upon successful completion of this unit, you will be able to:
- describe counting, permutation, and combination rules;
- compute the number of permutations and combinations of the members of a given set; and
- determine the number of all possible outcomes of a collection of events.
2.1: Rule of Products
If there is some number of different operations, and each operation can be performed in different ways, how many combinations of operations can be performed when the operations are not dependent on one another? This is an important question when trying to determine the number of outcomes for which one must account.
2.2: Permutations
Often it is the case that the order of things is not important. That is where permutations come in. It enables us to show how many different arrangements can be had of a given set of elements. Of course, this is not true of something like an event stream but we will discuss those later.
2.3: Partitions of Sets and the Law of Addition
In how many ways can a set be partitioned, broken into subsets, while assuming the independence of elements and ensuring that each element appears in only one subset? This question is often answered, for instance, when deciding how to partition workload across a network of computers. As systems become increasingly complex, the answer allows us to make best use of available resources.
2.4: Combinations and the Binomial Theorem
We now consider subsets of a given size. How many subsets of a given size can be created from the elements of a given set when order is not a concern? This is a good question when deciding how to partition supply to meet demand when a given number of units are required, without specifying which units.
Unit 2 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.