Combinatorics

You may have learned previously 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: We won't explore the concepts of P and NP directly at all in this course (though they will be mentioned a few times). if you have studied these ideas in computer science courses, you 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 researcher 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\text{,}\) 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\text{.}\)