tailieunhanh - Ebook Discrete mathematics and its applications (6th edition): Part 2

(BQ) Part 2 book "Discrete mathematics and its applications" has contents: Advanced counting techniques, relations, trees, boolean algebra, modelling computation. Please refer to the detailed content. | Recurrence Relations Solving Linear Recurrence Relations Divide-and-Conquer Algorithms and Recurrence Relations Generating Functions Inclusion-Exclusion Applications of Inclusion-Exclusion Advanced Counting Techniques Many counting problems cannot be solved easily using the methods discussed in Chapter 5. One such problem is How many bit strings of length n do not contain two consecutive zeros To solve this problem let a be the number of such strings of length n. An argument can be given that shows 1 a a _ . This equation called a recurrence relation and the initial conditions 1 2 and 2 3 determine the sequence . Moreover an explicit formula can be found for a from the equation relating the terms of the sequence. As we will see. a similar technique can be used to solve many different types of counting problems. We will also see that many counting problems can be solved using formal power series called generating functions where the coefficients of powers represent terms of the sequence we are interested in. Besides solving counting problems we will also be able to use generating functions to solve recurrence relations and to prove combinatorial identities. Many other kinds of counting problems cannot be solved using the techniques discussed in Chapter 5. such as How many ways are there to assign seven jobs to three employees so that each employee is assigned at least one job How many primes are there less than 1000 Both of these problems can be solved by counting the number of elements in the union of sets. We will develop a technique called the principle of inclusion-exclusion that counts the number of elements in a union of sets and we will show how this principle can be used to solve counting problems. The techniques studied in this chapter together with the basic techniques of Chapter 5 can be used to solve many counting problems. Recurrence Relations Introduction The number of bacteria in a colony doubles every hour. If a .