Discrete Mathematics: Elementary and Beyond

2.2 Comparing and Estimating Numbers 31 language of calculus, we have (n 2 ) n →∞ (n→∞). Here is another simple question: Which ...

32 2. Combinatorial Tools Both of the funny irrational numberseandπoccur in the same formula! Let us return to the question: How ...

2.3 Inclusion-Exclusion 33 So suppose that somebody records picture collecting data of the class in a table like Table 2.1 below ...

34 2. Combinatorial Tools n-set with an even number of elements is the same as the number of subsets with an odd number of eleme ...

2.4 Pigeonholes 35 inhabitants of New York. Can we now answer our original question? Yes. If there were no two people with the s ...

36 2. Combinatorial Tools The side of the square is obviously 10 cm, the diagonals of it are equal, and (from the Pythagorean Th ...

2.5 The Twin Paradox and the Good Old Logarithm 37 assumptions, we argued until we got a contradiction. This form of proof is ca ...

38 2. Combinatorial Tools useful to get upper and lower bounds by a method that will work in a more general case, when we havenp ...

2.5 The Twin Paradox and the Good Old Logarithm 39 –2 –1 0 1 12 3 FIGURE 2.3. The graph of the natural logarithm function. Note ...

40 2. Combinatorial Tools and hence ln ( nk n(n−1)···(n−k+1) ) ≥ 1 n + 2 n +···+ k− 1 n = 1 n (1 + 2 +···+(k−1)) = k(k−1) 2 n (r ...

2.5 The Twin Paradox and the Good Old Logarithm 41 Review Exercises 2.5.1What is the following sum? 1 1 · 2 + 1 2 · 3 + 1 3 · 4 ...

42 2. Combinatorial Tools 2.5.7We select 38 even positive integers, all less than 1000. Prove that there will be two of them who ...

3 Binomial Coefficients and Pascal’s Triangle 3.1 The Binomial Theorem In Chapter 1 we introduced the numbers (n k ) and called ...

44 3. Binomial Coefficients and Pascal’s Triangle choosex, say, 2 times, then we must choosey3 times, and so we getx^2 y^3. How ...

3.2 Distributing Presents 45 3.2 Distributing Presents...................... Suppose we havendifferent presents, which we want t ...

46 3. Binomial Coefficients and Pascal’s Triangle (a)n=k,n 1 =n 2 =···=nk=1; (b) n 1 =n 2 =···=nk− 1 =1,nk=n−k+1; (c) k=2; (d) k ...

3.3 Anagrams 47 But one would have to write a book to introduce an exciting character, ROBIN COSMICAT, who enforces a COSMIC RIO ...

48 3. Binomial Coefficients and Pascal’s Triangle ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ Alice Bob Carl Diane FIGURE 3.2. How to distributenpen ...

3.5 Pascal’s Triangle 49 ing trick, we can reduce the problem of counting such distributions to the problem we just solved: We b ...

50 3. Binomial Coefficients and Pascal’s Triangle We can replace each binomial coefficient by its numerical value to get another ...