• Unit 8: Combinatorics

    In this unit, you will learn to count. That is, you will learn to classify the objects of a set in such a way that one of several principles applies.

    Completing this unit should take you approximately 11 hours.

    • Upon successful completion of this unit, you will be able to:

      • distinguish between situations in which sampling with replacement is appropriate and those in which sampling without replacement should be used as well as the effect each has on the number of outcomes arising in various applications;
      • use the inclusion-exclusion principle to solve a variety of counting problems;
      • use the pigeon-hole principle in various settings; and
      • recognize when a counting problem requires the use combinations, permutations, or some other combinatorial object.

    • 8.1: Counting Problems as Sampling Problems with Conditions on the Structure of the Sample

    • 8.2: The Inclusion-Exclusion Principle

      • Inclusion/Exclusion Page

        Watch these videos for for an introduction to the inclusion/exclusion principle and an example of the principle. Notice that the problem is about As, Bs, and Cs, not As, Bs, and Os as the teacher describes at the start.

    • 8.3: The Pigeon-Hole Principle (PHP)

      • 8.3.1: The Standard Principle

        • Pigeon Hole Principle Page

          Watch this video, which provides a careful introduction to the pigeon-hole principle and several examples.

      • 8.3.2: Using the PHP Idea in Other Settings

        • Pigeon-hole Principle Problem Examples Page

          Watch these videos. The first video provides some an application of the pigeon-hole principle to divisibility and modular arithmetic. The second video provides some applications of the pigeon-hole principle to operations involving integers.

        • Basic Pigeon-Hole Principle Problems Page

          Watch this video, which provides some very elementary applications of the pigeon-hole principle.