Counting l 2 The division rule We can count the number of people in a room by counting ears and dividing by two Or we could count the number of fingers and divide by 10. Or we could count the number of fingers and toes and divide by 20. (Someone is probably short a finger or has an extra ear, but let's not worry about that right now. These observations lead to an important counting rule a k-to-1 function maps exactly k elements of the domain to every element of the range For example, the function mapping each ear to its owner is 2-to-1 t person A B ear 6 Similarly, the function mapping each finger to its owner is 10-to-1. And the function maping each each finger or toe to its owner is 20-to-1. Now just as a bijection implies two sets are the same size, a k-to-1 function implies that the domain is k times larger than the domain. Rule 2(Division Rule). If f: A-B is k-to-1, then [Al=k. BI Suppose A is the set of ears in the room and B is the set of people. Since we know there is a 2-to-1 mapping from ears to people, the Division Rule says that [A =2. B or, equivalently, B= Al /2. Thus, the number of people is half the number of ears Now this might seem like a stupid way to count people. But, surprisingly, many count- ing problems are made much easier by initially counting every item multiple times and then correcting the answer using the Division Rule. Let's look at some examples 2.1 Another chess problem In how many different ways can you place two identical rooks on a chessboard so that they do not share a row or column? A valid configuration is shown below on the left, and� � � Counting II 5 2 The Division Rule We can count the number of people in a room by counting ears and dividing by two. Or we could count the number of fingers and divide by 10. Or we could count the number of fingers and toes and divide by 20. (Someone is probably short a finger or has an extra ear, but let’s not worry about that right now.) These observations lead to an important counting rule. A k­to­1 function maps exactly k elements of the domain to every element of the range. For example, the function mapping each ear to its owner is 2­to­1: ear 1 - person A 3 ear 2  PPPPPP  ear 3  q person B �  ear 4 q person C ear 5 PPP � - PPP ear 6 � Similarly, the function mapping each finger to its owner is 10­to­1. And the function maping each each finger or toe to its owner is 20­to­1. Now just as a bijection implies two sets are the same size, a k­to­1 function implies that the domain is k times larger than the domain: Rule 2 (Division Rule). If f : A → B is k­to­1, then |A| = k B· | |. Suppose A is the set of ears in the room and B is the set of people. Since we know there is a 2­to­1 mapping from ears to people, the Division Rule says that |A| = 2 · |B| or, equivalently, |B| = | | A /2. Thus, the number of people is half the number of ears. Now this might seem like a stupid way to count people. But, surprisingly, many count￾ing problems are made much easier by initially counting every item multiple times and then correcting the answer using the Division Rule. Let’s look at some examples. 2.1 Another Chess Problem In how many different ways can you place two identical rooks on a chessboard so that they do not share a row or column? A valid configuration is shown below on the left, and