Discrete Mathematics: Elementary and Beyond

1.3 The Number of Subsets 11 contains the third (and in this case last) question you have to answer to determine the subset: Isc ...

12 1. Let’s Count! subset is “encoded” by a string of length 3, consisting of 0’s and 1’s. If we specify any such string, we can ...

1.3 The Number of Subsets 13 ann-element set correspond to integers, starting with 0 and ending with the largest integer that ha ...

14 1. Let’s Count! A correspondence with these properties is called aone-to-one correspon- dence(orbijection). If we can make a ...

1.5 Sequences 15 Now we can write 2^100 in the form 10x, onlyxwill not be an integer: the appropriate value ofxisx=lg2^100 = 100 ...

16 1. Let’s Count! these will be very difficult to pronounce, and are not likely to occur, but let’s count all of them as possib ...

1.6 Permutations 17 1.5.6We have 20 kinds of presents; this time, we have a large supply of each kind. We want to give presents ...

18 1. Let’s Count! second? abc acb bac bca cab cba bacabc a b c first? second? second? FIGURE 1.3. A decision tree for selecting ...

1.7 The Number of Ordered Subsets 19 1.7 The Number of Ordered Subsets At a competition of 100 athletes, only the order of the f ...

20 1. Let’s Count! 1.8 The Number of Subsets of a Given Size From here, we can easily derive one of the most important counting ...

1.8 The Number of Subsets of a Given Size 21 Ifn, k > 0 , then ( n− 1 k− 1 ) + ( n− 1 k ) = ( n k ) ; (1.8) ( n 0 ) + ( n 1 ) ...

22 1. Let’s Count! Review Exercises 1.8.8In how many ways can you seat 12 people at two round tables with 6 places each? Think o ...

1.8 The Number of Subsets of a Given Size 23 1.8.20LetAbe a set and let
A 2  denote the set of all 2-element subsets ofA. Whic ...

24 1. Let’s Count! 1.8.29What is the number of ways to colornobjects with 3 colors if every color must be used at least once? 1. ...

2 Combinatorial Tools 2.1 Induction It is time to learn one of the most important tools in discrete mathematics. We start with a ...

26 2. Combinatorial Tools this for the first 10 values ofn; can we be sure that it is valid for all? Well, I’d say we can be rea ...

2.1 Induction 27 ThePrinciple of Inductionsays that if (a) and (b) are true, then every natural number has the property. This is ...

28 2. Combinatorial Tools 1+2+3+4+5 =? 2(1+2+3+4+5) = 5.6 = 30 FIGURE 2.1. The sum of the firstnintegers 2.1.5Prove the followin ...

2.1 Induction 29 result we wanted to get, but after giving the argument once or twice, we said “etc.” instead of further repetit ...

30 2. Combinatorial Tools Now here (n−1)nis odd by the induction hypothesis, and 2nis even. Hencen(n+ 1) is the sum of an odd nu ...