4: Bijections and Combinatorial Proofs

Last updated
Save as PDF

Page ID: 60204

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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

You may recall that in Math 2000 you learned that two sets have the same cardinality if there is a bijection between them. (A bijection is a one-to-one, onto function.) This leads us to another important method for counting a set: we come up with a bijection between the elements of the unknown set, and the elements of a set that we do know how to count. This idea is very closely related to the concept of a combinatorial proof, which we will explore in the second half of this chapter.

Aside: Although we won’t explore the concepts of \(P\) and \(NP\) at all in this course, those of you who have studied these ideas in computer science courses may be interested to learn that most of the techniques used to prove that a particular problem is in \(P\) or in \(NP\) are related to the techniques discussed in this chapter. Usually, a problem \(X\) is proven to be in \(NP\) (for example) by starting with a problem \(Y\) that is already known to be in \(NP\). Then the scientist uses some clever ideas to show that problem \(Y\) can be related to problem \(X\) in such a way that if problem \(X\) could be solved in polynomial time, that solution would produce a solution to problem \(Y\), still in polynomial time. Thus the fact that \(Y\) is in \(NP\) forces \(X\) to be in \(NP\) also. The same ideas may sometimes relate the number of solutions of problem \(X\) to the number of solutions of problem \(Y\).

4.1: Counting via Bijections
It can be hard to figure out how to count the number of outcomes for a particular problem. Sometimes it will be possible to find a different problem, and to prove that the two problems have the same number of outcomes. If we can work out how to count the outcomes for the second problem, then we’ve also solved the first problem! This may seem blatantly obvious intuitively, but this technique can provide simple solutions to problems that at first glance seem very difficult.
4.2: Combinatorial Proofs
When we looked at bijections, we were using this idea to find an easier way to count something that seemed difficult. But if we actually can find a formula that counts the answer to our problem correctly in some difficult way, and we can also find a different formula that counts the answer to the same problem correctly by looking at it in a different way, then we know that the values of the two formulas must be equal, despite their different apperances. This is the idea of combinatorial proof.
4.3: Summary
This page contains the summary of the topics covered in Chapter 4.