10: Other Basic Counting Techniques

Last updated
Save as PDF

Page ID: 60120

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

There are two other elementary techniques that are surprisingly useful even in quite difficult counting problems. We will wrap up our exploration of enumeration by discussing these techniques.

10.1: The Pigeonhole Principle
The Pigeonhole Principle is a technique that you can apply when you are faced with items chosen from a number of different categories of items, and you want to know whether or not some of them must come from the same category, without looking at all of the items.
10.2: Inclusion-Exclusion
We could draw a very basic Venn diagram showing the kinds of trees that are growing at the various houses on my street. Naively, you might think that adding these together would give us the total number of houses with trees. However, in order to work out the number of houses that have trees, we must add the number that have deciduous trees to the number that have evergreen trees and then subtract the number that have both kinds of trees. This is the idea of “inclusion-exclusion.”
10.3: Summary
This page contains the summary of the topics covered in Chapter 10.