6.042/18.] Mathematics for Computer Science March 25, 2005 Srini devadas and Eric Lehman Lecture notes Counting I 20480135385502964448038317100483217350139411301757632573310834796474093988247331000042995311646021 489445991866915676240992320823442159736864701926558009491235489891226286638496243997123475922766310 1082662032430379651370981343725465635515786486911360429008011992802180260018518399140676002660747477 1178480894769706178994993357488339305865392371136561161717891377378967014058543691283470191452333763 25312735168323969385132736449099460404801899691496144868973001582369723512867530925837137092461352 1301505129234077811069011379004413273708409441724662473145938511692347461528694321112363996867296665 311567111143866433882194387033212743797135532281568144289442668749634882748772321203608477245851154 14700294527212035876862144080505804577801451363100687085294554388684914788187914221617225825463410 1578271047286257499433886416728346102570234812492069149555081209500937323979062628024592126283973285 1638243921852176243192354423599683112377778821124969496324513659871524235419137845566925526349897794 1763580219131985963102365467093944574943904211122071282111436136198284156509153762966803189291934419 1826227795601842231029694481537935186538427961342771739200836518623079253949270880194077636406984249 1843971862675102037201420483705294821292260444219072156548742117556762205879324301480722103490379204 239695119372213452617723751063894238550185506715307256928471643910402330509436090832146695147140581 2781394568268599801096354514236819200476921806991073328226570752354316203179475308159734538249013238 2796605196713610405408019518123409613014408404185674264418295415734449641399492376623917486974923202 2931016394761975263190347519826739812561799439134876321981265318093271863219511972558779880288252979 2933458058294405155197296531759294031623121975837277121544322119128823105119602413424619187112552264 3075514410490975920315348538435812677179412835694778589186642402623566100109631217114906129219461111 3111474985252793452860017543921171224890199542344178981567867632129631786799908189853102753335981319 3145621587936120118438701561037982609283819276045881475910170375733378486169913237476341764299813987 314890125562888110319854956323175554652286776760448149436716871371161932035 315769310532511128432199356921683746370196174237128176063831682536571306791 Two different subsets of the ninety 25-digit numbers shown above have the same sum For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column. Can you find two such subsets? This is a very difficult computational problem. But we'll prove that such subsets must exist! This is the sort of weird conclusion one can reach by tricky use of counting, the topic of this chapter Counting seems easy enough: 1, 2, 3, 4, etc. This explicit approach works well for counting simple things, like your toes, and for extremely complicated things for which there's no identifiable structure. However, subtler methods can help you count many things in the vast middle ground, such as The number of different ways to select a dozen doughnuts when there are five vari eties available The number of 16-bit numbers with exactly 4 ones Counting is useful in computer science for several reason Determining the time and storage required to solve a computational problem-a central objective in computer science- often comes down to solving a counting
6.042/18.062J Mathematics for Computer Science March 25, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting I 20480135385502964448038 3171004832173501394113017 5763257331083479647409398 8247331000042995311646021 489445991866915676240992 3208234421597368647019265 5800949123548989122628663 8496243997123475922766310 1082662032430379651370981 3437254656355157864869113 6042900801199280218026001 8518399140676002660747477 1178480894769706178994993 3574883393058653923711365 6116171789137737896701405 8543691283470191452333763 1253127351683239693851327 3644909946040480189969149 6144868973001582369723512 8675309258374137092461352 1301505129234077811069011 3790044132737084094417246 6247314593851169234746152 8694321112363996867296665 1311567111143866433882194 3870332127437971355322815 6814428944266874963488274 8772321203608477245851154 1470029452721203587686214 4080505804577801451363100 6870852945543886849147881 8791422161722582546341091 1578271047286257499433886 4167283461025702348124920 6914955508120950093732397 9062628024592126283973285 1638243921852176243192354 4235996831123777788211249 6949632451365987152423541 9137845566925526349897794 1763580219131985963102365 4670939445749439042111220 7128211143613619828415650 9153762966803189291934419 1826227795601842231029694 4815379351865384279613427 7173920083651862307925394 9270880194077636406984249 1843971862675102037201420 4837052948212922604442190 7215654874211755676220587 9324301480722103490379204 2396951193722134526177237 5106389423855018550671530 7256932847164391040233050 9436090832146695147140581 2781394568268599801096354 5142368192004769218069910 7332822657075235431620317 9475308159734538249013238 2796605196713610405408019 5181234096130144084041856 7426441829541573444964139 9492376623917486974923202 2931016394761975263190347 5198267398125617994391348 7632198126531809327186321 9511972558779880288252979 2933458058294405155197296 5317592940316231219758372 7712154432211912882310511 9602413424619187112552264 3075514410490975920315348 5384358126771794128356947 7858918664240262356610010 9631217114906129219461111 3111474985252793452860017 5439211712248901995423441 7898156786763212963178679 9908189853102753335981319 3145621587936120118438701 5610379826092838192760458 8147591017037573337848616 9913237476341764299813987 3148901255628881103198549 5632317555465228677676044 8149436716871371161932035 3157693105325111284321993 5692168374637019617423712 8176063831682536571306791 Two different subsets of the ninety 25digit numbers shown above have the same sum. For example, maybe the sum of the numbers in the first column is equal to the sum of the numbers in the second column. Can you find two such subsets? This is a very difficult computational problem. But we’ll prove that such subsets must exist! This is the sort of weird conclusion one can reach by tricky use of counting, the topic of this chapter. Counting seems easy enough: 1, 2, 3, 4, etc. This explicit approach works well for counting simple things, like your toes, and for extremely complicated things for which there’s no identifiable structure. However, subtler methods can help you count many things in the vast middle ground, such as: • The number of different ways to select a dozen doughnuts when there are five varieties available. • The number of 16bit numbers with exactly 4 ones. Counting is useful in computer science for several reasons: • Determining the time and storage required to solve a computational problem— a central objective in computer science— often comes down to solving a counting problem
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 function
2 Counting I • Counting is the basis of probability theory, which in turn is perhaps the most important 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. Formally, 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:
Counting I domain b 2 codomain cde In this example, the domain is the set fa,b, c, d, el and the range is the set Y= (1, 2, 3, 4, 5/. Related elements are joined by an arrow. This relation is a function because every element on the left is related to exactly one element on the right. In graph-theoretic terms, this is a function because every element on the left has degree exactly 1. If r is an element of the domain, then the related element in the codomain is denoted f(). w often say f maps r to f (a). In this case, f maps a to 1, b to 3, c to 4, d to 3 and e to 5 lently, f(a)=l, f(b)=3, f(c)=4, f(d)=3, and f(e)=5 The relations shown below are not functions. 12345 12345 The relation on the left is not a function because a is mapped to two elements of the codomain. The relation on the right is not a function because b and d are mapped to zero elements of the codomain. Tsk-tsk 1.2 Bijections The definition of a function is rather asymmetric; there are restrictions on elements in the domain, but not on elements in the codomain. a bijection or bijective function is a function f: X- Y that maps exactly one element of the domain to each element of the codomain. In graph terms, both domain and codomain elements are required to hav degree exactly 1 in a bijective function. Here is an example of a bijection
Counting I 3 X f Y a - 1 domain b PP 2 codomain PPPPq c 3 P P1 PPPP d q 4 e - 5 In this example, the domain is the set X = {a, b, c, d, e} and the range is the set Y = {1, 2, 3, 4, 5}. Related elements are joined by an arrow. This relation is a function because every element on the left is related to exactly one element on the right. In graphtheoretic terms, this is a function because every element on the left has degree exactly 1. If x is an element of the domain, then the related element in the codomain is denoted f(x). We often say f maps x to f(x). In this case, f maps a to 1, b to 3, c to 4, d to 3 and e to 5. Equivalently, f(a) = 1, f(b) = 3, f(c) = 4, f(d) = 3, and f(e) = 5. The relations shown below are not functions: X Y X Y a P - PPPPPq b c P P PPPPPq PPPPPq d 1 1 2 3 4 a b c d - PPPPPPq 1 2 3 4 e - 5 e - 5 The relation on the left is not a function because a is mapped to two elements of the codomain. The relation on the right is not a function because b and d are mapped to zero elements of the codomain. Tsktsk! 1.2 Bijections The definition of a function is rather asymmetric; there are restrictions on elements in the domain, but not on elements in the codomain. A bijection or bijective function is a function f : X Y → that maps exactly one element of the domain to each element of the codomain. In graph terms, both domain and codomain elements are required to have degree exactly 1 in a bijective function. Here is an example of a bijection:
domain 2 codomain In contrast, these relations that are not bijections b b 4 The first function is not bijective because 3 is related to two elements of the domain. The second function is not bijective because 4 is related to zero elements of the domain. The last relation is not even a function because b is associated with zero elements of the domain Bijective functions are also found in the more-familiar world of real-valued functions For example, f(a)=6.c+5 is a bijective function with domain and codomain R For every real number y in the codomain, f(a)=y for exactly one real number a in the domain. On the other hand, f(r)=x2 is not a bijective function. The number 4 in the codomain is related to both 2 and -2 in the domain 1. 3 The bijection Rule If we can pair up all the girls at a dance with all the boys, then there must be an equal number of each. This simple observation generalizes to a powerful counting rule Rule 1(Bijection Rule). If there exists a bijection f: A- B, then A=B In the example, A is the set of boys, B is the set of girls, and the function f defines how they are paired The Bijection Rule acts as a magnifier of counting ability; if you figure out the size of one set, then you can immediately determine the sizes of many other sets via bijections
� � � 4 Counting I X f Y a PP 1 PPPP domain �q b PP 2 codomain c P �PPqP PP 3 PPPPq d � 4 e - 5 In contrast, these relations that are not bijections: X Y X Y X Y a - 1 a - 1 a - 1 b c P PPPPPPq PPPPPq d 3 e 3 2 3 4 b c PPPPPPq QQQQQQs d 3 2 3 4 5 b c d e PPPPPPq 3 3 2 3 4 The first function is not bijective because 3 is related to two elements of the domain. The second function is not bijective because 4 is related to zero elements of the domain. The last relation is not even a function, because b is associated with zero elements of the domain. Bijective functions are also found in the morefamiliar world of realvalued functions. For example, f(x) = 6x+5 is a bijective function with domain and codomain R. For every real number y in the codomain, f(x) = y for exactly one real number x in the domain. On the other hand, f(x) = x2 is not a bijective function. The number 4 in the codomain is related to both 2 and 2 in the domain. 1.3 The Bijection Rule If we can pair up all the girls at a dance with all the boys, then there must be an equal number of each. This simple observation generalizes to a powerful counting rule: Rule 1 (Bijection Rule). If there exists a bijection f : A → B, then |A| = | | B . In the example, A is the set of boys, B is the set of girls, and the function f defines how they are paired. The Bijection Rule acts as a magnifier of counting ability; if you figure out the size of one set, then you can immediately determine the sizes of many other sets via bijections
Counting I For example, let's return to two sets mentioned earlier A=all ways to select a dozen doughnuts when five varieties are available B=all 16-bit sequences with exactly 4 ones Lets consider a particular element of set a: 00000000.00 chocolate lemon-filled sugar Weve depicted each doughnut with a 0 and left a gap between the different varieties Thus, the selection above contains two chocolate doughnuts, no lemon-filled, six sugar, two glazed and two plain. Now let's put a 1 into each of the four gaps 001 1000000100.100 sugar glazed Weve just formed a 16-bit number with exactly 4 ones--an element of B i,. This example suggests a bijection from set A to set B: map a dozen doughnuts consist- of: c chocolate, l lemon-filled, s sugar, g glazed, and p plain to the sequence 010:0 01010 The resulting sequence always has 16 bits and exactly 4 ones, and thus is an element of B. Moreover, the mapping is a bijection; every such bit sequence is mapped to by exactly one order of a dozen doughnuts. Therefore, A=B by the Bijection Rule! This demonstrates the magnifying power of the bijection rule. We managed to prove that two very different sets are actually the same size- even though we dont know exactly how big either one is. But as soon as we figure out the size of one set, we'll immediately know the size of the other. This particular bijection might seem frighteningly ingenious if you,ve not seen it be- fore. But you'll use essentially this same argument over and over and over, and soon you'll consider it boringly routine 1.4 Sequence The Bijection Rule lets us count one thing by counting another. This suggests a general t really good at counting just a few things and then use bijections to count Python
Counting I 5 For example, let’s return to two sets mentioned earlier: A = all ways to select a dozen doughnuts when five varieties are available B = all 16bit sequences with exactly 4 ones Let’s consider a particular element of set A: 0 0 0 0 0 0 0 0 � 0 0 0 0 ���� ���� � �� ���� ���� chocolate lemonfilled sugar glazed plain We’ve depicted each doughnut with a 0 and left a gap between the different varieties. Thus, the selection above contains two chocolate doughnuts, no lemonfilled, six sugar, two glazed, and two plain. Now let’s put a 1 into each of the four gaps: ���� 1 0 0 0 0 0 0 � 0 0 1 1 0 0 1 0 0 ���� � �� ���� ���� chocolate lemonfilled sugar glazed plain We’ve just formed a 16bit number with exactly 4 ones— an element of B! This example suggests a bijection from set A to set B: map a dozen doughnuts consisting of: c chocolate, l lemonfilled, s sugar, g glazed, and p plain to the sequence: � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 �� � �� � �� � �� � �� � c l s g p The resulting sequence always has 16 bits and exactly 4 ones, and thus is an element of B. Moreover, the mapping is a bijection; every such bit sequence is mapped to by exactly one order of a dozen doughnuts. Therefore, |A| = | | B by the Bijection Rule! This demonstrates the magnifying power of the bijection rule. We managed to prove that two very different sets are actually the same size— even though we don’t know exactly how big either one is. But as soon as we figure out the size of one set, we’ll immediately know the size of the other. This particular bijection might seem frighteningly ingenious if you’ve not seen it before. But you’ll use essentially this same argument over and over and over, and soon you’ll consider it boringly routine. 1.4 Sequences The Bijection Rule lets us count one thing by counting another. This suggests a general strategy: get really good at counting just a few things and then use bijections to count everything else:
Counting I sequence-counting problems bijection all counting problems This is precisely the strategy we'll follow. In particular, we'll get really good at count ing sequences. When we want to determine the size of some other set T, we'll find a bi jection from T to a set of sequences S. Then we'll use our super-ninja sequence-counting skills to determine ISl, which immediately gives us T We'll need to hone this idea omewhat as we go along, but that's pretty much the plan In order to pull this off, we need to clarify some issues concerning sequences and sets Recall that a set is an unordered collection of distinct elements. A set is often represented by listing its elements inside curly-braces. For example, a, b, c is a set, and ic, b, a is another way of writing the same set. On the other hand, a, b, a is not a set, because element a appears twice On the other hand, a sequence is an ordered collection of elements(called components or terms) that are not necessarily distinct. A sequence is often written by listing the terms inside parentheses. For example, (a, b, c)is a sequence, and (c, b, a) is a different sequence Furthermore(a,b, a) is a perfectly valid three-term sequence The distinction between sets and sequences is crucial for everything that follows. If you dont keep the distinction clear in your mind, you re doomed 2 Two Basic Counting rules We'll harvest our first crop of counting problems with two basic rules 2.1 The Sum rule Linus allocates his big sister Lucy a quota of 20 crabby days, 40 irritable days, and 60 generally surly days. On how many days can lucy be out-of-sorts one way or another Let set C be her crabby days I be her irritable days and s be the generally surly. In these terms, the answer to the question is CUIUS]. Now assuming that she is permitted at most one bad quality each day, the size of this union of sets is given by the Sum rule
6 Counting I problems sequence−counting S T all counting problems bijection This is precisely the strategy we’ll follow. In particular, we’ll get really good at counting sequences. When we want to determine the size of some other set T, we’ll find a bijection from T to a set of sequences S. Then we’ll use our superninja sequencecounting skills to determine |S|, which immediately gives us | | T . We’ll need to hone this idea somewhat as we go along, but that’s pretty much the plan! In order to pull this off, we need to clarify some issues concerning sequences and sets. Recall that a set is an unordered collection of distinct elements. A set is often represented by listing its elements inside curlybraces. For example, {a, b, c} is a set, and {c, b, a} is another way of writing the same set. On the other hand, {a, b, a} is not a set, because element a appears twice. On the other hand, a sequence is an ordered collection of elements (called components or terms) that are not necessarily distinct. A sequence is often written by listing the terms inside parentheses. For example, (a, b, c) is a sequence, and (c, b, a) is a different sequence. Furthermore (a, b, a) is a perfectly valid threeterm sequence. The distinction between sets and sequences is crucial for everything that follows. If you don’t keep the distinction clear in your mind, you’re doomed! 2 Two Basic Counting Rules We’ll harvest our first crop of counting problems with two basic rules. 2.1 The Sum Rule Linus allocates his big sister Lucy a quota of 20 crabby days, 40 irritable days, and 60 generally surly days. On how many days can Lucy be outofsorts one way or another? Let set C be her crabby days, I be her irritable days, and S be the generally surly. In these terms, the answer to the question is | | C ∪ I ∪ S . Now assuming that she is permitted at most one bad quality each day, the size of this union of sets is given by the Sum Rule:
Counting I Rule 2(Sum Rule). If A1, A2, .. An are disjoint sets, then JA1 U A2U... U An=A1+A2+.+Anl Thus, according to Linus budget, Lucy can be out-of-sorts for: CUI∪Sl=C|U|U|s 120 days Notice that the Sum Rule holds only for a union of disjoint sets. Finding the size of a union of intersecting sets is a more complicated problem that we'll take up later 2.2 The product rule The product rule gives the size of a product of sets. Recall that if Pi, P2,..., Pn are sets, then P1×P2 is the set of all sequences whose first term is drawn from Pi, second term is drawn from P and so forth Rule 3 (Product Rule). If P1, P2,... Pn are sets, then P×P2×….×Pn|=|f|·|P2|…|P Unlike the sum rule, the product rule does not require the sets Pi,..., Pn to be disjoint For example, suppose a daily diet consists of a breakfast selected from set B, a lunch from set L, and a dinner from set D pancakes, bacon and eggs L=burger and fries, garden salad, Doritos D=macaroni, pizza, frozen burrito, pasta, Doritos) Then BXLX Dis the set of all possible daily diets. Here are some sample elements pancakes, burger and frie es. pizza (bacon and eggs, garden salad, pasta) (Doritos, Doritos, frozen burrito) The Product rule tells us how many different daily diets are possible B×L×D|=|B·|L·
Counting I 7 Rule 2 (Sum Rule). If A1, A2, . . . , An are disjoint sets, then: |A1 ∪ A2 ∪ . . . ∪ An| | | | | | = A1 + A2 + . . . + An| Thus, according to Linus’ budget, Lucy can be outofsorts for: | | C ∪ I ∪ S = | | ∪ | | ∪ | | C I S = 20 + 40 + 60 = 120 days Notice that the Sum Rule holds only for a union of disjoint sets. Finding the size of a union of intersecting sets is a more complicated problem that we’ll take up later. 2.2 The Product Rule The product rule gives the size of a product of sets. Recall that if P1, P2, . . . , Pn are sets, then P1 × P2 × . . . × Pn is the set of all sequences whose first term is drawn from P1, second term is drawn from P2 and so forth. Rule 3 (Product Rule). If P1, P2, . . . Pn are sets, then: |P1 × P2 × . . . × Pn| = | | · | P1 P2| · · · |Pn| Unlike the sum rule, the product rule does not require the sets P1, . . . , Pn to be disjoint. For example, suppose a daily diet consists of a breakfast selected from set B, a lunch from set L, and a dinner from set D: B = {pancakes, bacon and eggs, bagel, Doritos} L = {burger and fries, garden salad, Doritos} D = {macaroni, pizza, frozen burrito, pasta, Doritos} Then B × L × D is the set of all possible daily diets. Here are some sample elements: (pancakes, burger and fries, pizza) (bacon and eggs, garden salad, pasta) (Doritos, Doritos, frozen burrito) The Product Rule tells us how many different daily diets are possible: | | B × L × D = |B| · | | · | L D| = 4 3 5 · · = 60
Counting I 2.3 Putting rules Together Few counting problems can be solved with a single rule. More often, a solution is a flury of sums, products, bijections, and other methods. Let's look at some examples that bring more than one rule into play Passwords The sum and product rules together are useful for solving problems involving passwords, telephone numbers, and license plates. For example, on a certain computer system,a valid password is a sequence of between six and eight symbols. The first symbol must be a letter(which can be lowercase or uppercase), and the remaining symbols must be either letters or digits. How many different passwords are possible? Lets define two sets, corresponding to valid symbols in the first and subsequent posi tions in the password F={a,b,…,z,A,B,…,Z} S={a,b,…,z,A,B,…,Z,0,1,…,9} In these terms, the set of all possible passwords is (F×S5)u(F×S)U(F×S) Thus, the length-six passwords are in set Fx S5, the length-seven passwords are in FxS6, and the length-eight passwords are in FX S. Since these sets are disjoint, we can apply the Sum Rule and count the total number of possible passwords as follows (F×S)U(F×S0)U(F×S)=F×s+|F×S+|F×S( Sum rule FI SP+IF1. ISI+F1. S7 Product rule 625+52·626+52.627 ≈1.8·104 different passwords Subsets of an n-element set How many different subsets of an n element set X are there? For example, the set X Lc1, 12, Is has eight different subsets {}{x1}{x2}{x1,x2} {x3}{x1,x3}{x2,x3}{x1,x2,x3} There is a natural bijection from subsets of X to n-bit Let 1 the elements of X. Then a particular subset of X maps to the sequence(b1,., bn)
� � � � � � � � � � � � � � � � 8 Counting I 2.3 Putting Rules Together Few counting problems can be solved with a single rule. More often, a solution is a flury of sums, products, bijections, and other methods. Let’s look at some examples that bring more than one rule into play. Passwords The sum and product rules together are useful for solving problems involving passwords, telephone numbers, and license plates. For example, on a certain computer system, a valid password is a sequence of between six and eight symbols. The first symbol must be a letter (which can be lowercase or uppercase), and the remaining symbols must be either letters or digits. How many different passwords are possible? Let’s define two sets, corresponding to valid symbols in the first and subsequent positions in the password. F = {a, b, . . . , z, A, B, . . . , Z} S = {a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9} In these terms, the set of all possible passwords is: (F × S5 ) ∪ (F × S6 ) ∪ (F × S7 ) Thus, the lengthsix passwords are in set F ×S5, the lengthseven passwords are in F ×S6 , and the lengtheight passwords are in F × S7. Since these sets are disjoint, we can apply the Sum Rule and count the total number of possible passwords as follows: = F × S7 S Sum Rule 5 S6 S7 F × S5 F × S6 (F × ) ∪ (F × ) ∪ (F × ) + + 5 6 7 = |F| · | | S + |F S | · | | + |F S | · | | Product Rule = 52 · 625 + 52 626 + 52 627 · · ≈ 1.8 · 1014 different passwords Subsets of an nelement Set How many different subsets of an n element set X are there? For example, the set X = {x1, x2, x3} has eight different subsets: {} { { { x1} x2} x1, x2} {x3} {x1, x3} {x2, x3} {x1, x2, x3} There is a natural bijection from subsets of X to nbit sequences. Let x1, x2, . . . , xn be the elements of X. Then a particular subset of X maps to the sequence (b1, . . . , bn)
Counting I where bi= l if and only if Ti is in that subset. For example, if n= 10, then the subset (a2, I3, 5, 17, 11o) maps to a 10-bit sequence as follows subset. 2, sequence We just used a bijection to transform the original problem into a question about sequences- exactly according to plan! Now if we answer the sequence question, then weve solved our original problem as well But how many different n-bit sequences are there? For example, there are 8 different 3-bit sequences (0,0,0)(0,0,1) 0,1,0) (0,1,1 (1,0,0)(1,0,1)(1,1,0)(1,1,1) Well, we can write the set of all n-bit sequences as a product of sets {0,1}×{0,1}×…x{0,1}={0,1} Then Product Rule gives the answer {0,1}2=|{0,1yn This means that the number of subsets of an n-element set X is also 2n. Well put this 3 More Functions: Injections and Surjections Bijective functions are incredibly powerful counting tools. A few other kinds of functions are useful as well; we'll look at two now and one more next time. A function f: X-Y surjective if every element of Y is mapped to at least once injective if every element of y is mapped to at most once bijective if every element of r is mapped to exactly once Weve repeated the definition of a bijective function for comparison. Notice that these definitions immediately imply that a function is bijective if and only if it is both injectiv and surjective. Now the names"surjective"and"injective"are hopelessly unmemorable and nondescriptive. Some people prefer the terms onto and into, respectively, perhaps the grounds that these are hopelessly unmemorable and nondescriptive- but shorter. Anyway, here are a couple examples
� �� Counting I 9 where bi = 1 if and only if xi is in that subset. For example, if n = 10, then the subset {x2, x3, x5, x7, x10} maps to a 10bit sequence as follows: subset: x2, x3, x5, x7, x10 sequence: { ( 0, 1, 1, 0, 1, 0, 1, 0, 0, 1 } ) We just used a bijection to transform the original problem into a question about sequences— exactly according to plan! Now if we answer the sequence question, then we’ve solved our original problem as well. But how many different nbit sequences are there? For example, there are 8 different 3bit sequences: (0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1) Well, we can write the set of all nbit sequences as a product of sets: {0, 1}n {0, 1} × {0, 1} × . . . × {0, 1} =� n terms Then Product Rule gives the answer: |{0, 1} = n | |{0, 1}|n = 2n This means that the number of subsets of an nelement set X is also 2n. We’ll put this answer to use shortly. 3 More Functions: Injections and Surjections Bijective functions are incredibly powerful counting tools. A few other kinds of functions are useful as well; we’ll look at two now and one more next time. A function f : X Y → is: • surjective if every element of Y is mapped to at least once • injective if every element of Y is mapped to at most once • bijective if every element of Y is mapped to exactly once We’ve repeated the definition of a bijective function for comparison. Notice that these definitions immediately imply that a function is bijective if and only if it is both injective and surjective. Now the names “surjective” and “injective” are hopelessly unmemorable and nondescriptive. Some people prefer the terms onto and into, respectively, perhaps on the grounds that these are hopelessly unmemorable and nondescriptive— but shorter. Anyway, here are a couple examples:
Counting I xabcde 123 The function on the left is surjective(every element on the right is mapped to at least once), but not injective(element 3 is mapped to twice). The function on the right is injec- tive(every element is mapped to at most once), but not surjective(element 4 is mapped to zero times) Earlier, we observed that two sets are the same size if there is a bijection between them Similarly, surjections and injections imply certain size relationships between sets Rule 4 (Mapping Rule). 1.lf:X→ Y is surjective, then X≥|Y 2.Jf:X→ Y is injective,, then X≤|Y 3. Iff X- Y is bijective, then X=Y 3.1 The Pigeonhole Principle Here is an old puzzle many socks must you withdraw to be sure that you have a matching pair i A drawer in a dark room contains red socks, green socks, and blue socks. He For example, picking out three socks is not enough; you might end up with one red,one green, and one blue. The solution relies on the Pigeonhole Principle, which is a friendly name for the contrapositive of part ( 2)of the Mapping Rule. Let's write it down If X >Yl, then no function f X-Y is injective Now let's rewrite this a second time to eliminate the word"injective" since, by now, there's not a ghost of a chance that you remember what that means Rule 5(Pigeonhole Principle). IfIX>Y, then for every function f: X- Y there exist two different elements of X that are mapped to the same element of
10 Counting I X Y X Y a - 1 a - 1 3 2 3 2 b PPPPPP b PPPPPP c q 3 c Q q 3 3 Q PPPPPP d q d Q 4 Q 4 QQ e s 5 The function on the left is surjective (every element on the right is mapped to at least once), but not injective (element 3 is mapped to twice). The function on the right is injective (every element is mapped to at most once), but not surjective (element 4 is mapped to zero times). Earlier, we observed that two sets are the same size if there is a bijection between them. Similarly, surjections and injections imply certain size relationships between sets. Rule 4 (Mapping Rule). 1. If f : X → Y is surjective, then |X Y | ≥ | |. 2. If f : X → Y is injective, then |X Y | ≤ | |. 3. If f : X → Y is bijective, then |X| = | | Y . 3.1 The Pigeonhole Principle Here is an old puzzle: A drawer in a dark room contains red socks, green socks, and blue socks. How many socks must you withdraw to be sure that you have a matching pair? For example, picking out three socks is not enough; you might end up with one red, one green, and one blue. The solution relies on the Pigeonhole Principle, which is a friendly name for the contrapositive of part (2) of the Mapping Rule. Let’s write it down: If |X > Y | | |, then no function f : X Y → is injective. Now let’s rewrite this a second time to eliminate the word “injective” since, by now, there’s not a ghost of a chance that you remember what that means: Rule 5 (Pigeonhole Principle). If |X > | | |Y , then for every function f : X Y there exist two different elements of X that are mapped to the same element of Y . →