7: Proof Techniques III - Combinatorics
- Page ID
- 19408
\( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Tragedy is when I cut my finger. Comedy is when you fall into an open sewer and die.
–Mel Brooks
- 7.1: Counting
- The title of this section, “Counting,” is not intended to evoke the usual process of counting sheep, or counting change. What we want is to be able to count some collection in principle so that we will be able to discover a formula for its size. There are two principles that will be indispensable in counting things: the “multiplication rule” which tells us when we should multiply, and the “addition rule” which tells us when we should add.
- 7.2: Parity and Counting Arguments
- This section is concerned with two very powerful elements of the proofmaking arsenal: “Parity” is a way of referring to the result of an even/odd calculation; Counting arguments most often take the form of counting some collection in two different ways – and then comparing those results. These techniques have little to do with one another, but when they are applicable they tend to produce really elegant little arguments.
- 7.3: The Pigeonhole Principle
- The word “pigeonhole” can refer to a hole in which a pigeon roosts (i.e. pretty much what it sounds like) or a series of roughly square recesses in a desk in which one could sort correspondence. Whether you prefer to think of roosting birds or letters being sorted, the first and easiest version of the pigeonhole principle is that if you have more “things” than you have “containers” there must be a container holding at least two things.
- 7.4: The Algebra of Combinations
- A binomial is a polynomial with two terms. It seems likely that you will have already seen the arrangement of these binomial coefficients into a triangular array – known as Pascal’s triangle. The thing that makes this triangle so nice and that leads to the strange name “binomial coefficients” for the number of k-combinations of an n-set is that you can use the triangle to (very quickly) compute powers of binomials.