Counting functions and subsets
Very many counting problems can be formulated in terms of counting the number of functions between two sets (possibly satisfying certain properties) or counting the number of subsets of a given set (possibly satisfying certain properties). In this chapter we give a brief introduction to these ideas. They naturally lead to the binomial coefficients, one of the most important families of numbers in all mathematics.
Suppose that X and Y are finite sets. It is natural to ask how many different functions there are with domain X and codomain Y. For example, if X is a set of people and Y is a set of dishes on a menu, then each function X → Y represents a choice of (one) dish for each ...