Counting I Counting is the basis of probability theory, which in turn is perhaps the most im- portant topic this term Two remarkable proof techniques, the"pigeonhole principle"and"combinatorial proof", rely on counting. These lead to a variety of interesting and useful insights We re going to present a lot of rules for counting. These rules are actually theorems, but were generally not going to prove them. Our objective is to teach you counting as a practical skill, like integration. And most of the rules seem"obvious"anyway 1 Counting One Thing by Counting Another How do you count the number of people in a crowded room? We could count heads since for each person there is exactly one head. Alternatively, we could count ears and divide by two. Of course, we might have to adjust the calculation if someone lost an ear in a pirate raid or someone was born with three ears. The point here is that we can often count one thing by counting another, though some fudge factors may be required. This the central theme of counting, from the easiest problems to the hardest In more formal terms, every counting problem comes down to determining the size of some set. The size or cardinality of a set s is the number of elements in s and is denoted S]. In these terms, were claiming that we can often find the size of one set S by finding the size of a related set T. We already have a mathematical tool for relating one set to another relations. Not surprisingly, a particular kind of relation is at the heart of counting 1.1 Functions Functions like f(a)=22+l and g(a)=tan-(a)are surely quite familiar from calculus Were going to use functions for counting as well, but in a way that might not be familiar Instead of functions that map one real number to another, well use functions that relate elements of finite sets In order to count accurately, we need to carefully define the notion of a function. For mally, a function f: X- Y is a relation between two sets, X and Y, that relates ever element of X to exactly one element of Y. The set X is called the domain of the function f, and y is called the codomain. Here is an illustration of a function2 Counting I • Counting is the basis of probability theory, which in turn is perhaps the most im￾portant topic this term. • Two remarkable proof techniques, the “pigeonhole principle” and “combinatorial proof”, rely on counting. These lead to a variety of interesting and useful insights. We’re going to present a lot of rules for counting. These rules are actually theorems, but we’re generally not going to prove them. Our objective is to teach you counting as a practical skill, like integration. And most of the rules seem “obvious” anyway. 1 Counting One Thing by Counting Another How do you count the number of people in a crowded room? We could count heads, since for each person there is exactly one head. Alternatively, we could count ears and divide by two. Of course, we might have to adjust the calculation if someone lost an ear in a pirate raid or someone was born with three ears. The point here is that we can often count one thing by counting another, though some fudge factors may be required. This is the central theme of counting, from the easiest problems to the hardest. In more formal terms, every counting problem comes down to determining the size of some set. The size or cardinality of a set S is the number of elements in S and is denoted |S|. In these terms, we’re claiming that we can often find the size of one set S by finding the size of a related set T. We already have a mathematical tool for relating one set to another: relations. Not surprisingly, a particular kind of relation is at the heart of counting. 1.1 Functions Functions like f(x) = x2 + 1 and g(x) = tan−1(x) are surely quite familiar from calculus. We’re going to use functions for counting as well, but in a way that might not be familiar. Instead of using functions that map one real number to another, we’ll use functions that relate elements of finite sets. In order to count accurately, we need to carefully define the notion of a function. For￾mally, a function f : X Y → is a relation between two sets, X and Y , that relates every element of X to exactly one element of Y . The set X is called the domain of the function f, and Y is called the codomain. Here is an illustration of a function: