TAILIEUCHUNG - Lecture Discrete mathematics and its applications (7/e) – Chapter 8: Advanced counting techniques

This chapter presents the following content: Applications of recurrence relations, solving linear recurrence relations, divide-and-conquer algorithms and recurrence relations, generating functions, inclusion-Exclusion, applications of inclusion-exclusion. | Advanced Counting Techniques Chapter 8 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Applications of Recurrence Relations Solving Linear Recurrence Relations Homogeneous Recurrence Relations Nonhomogeneous Recurrence Relations Divide-and-Conquer Algorithms and Recurrence Relations Generating Functions Inclusion-Exclusion Applications of Inclusion-Exclusion Applications of Recurrence Relations Section Section Summary Applications of Recurrence Relations Fibonacci Numbers The Tower of Hanoi Counting Problems Algorithms and Recurrence Relations (not currently included in overheads) Recurrence Relations (recalling definitions from Chapter 2) Definition: A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, , an-1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. Rabbits and the Fiobonacci Numbers Example: A young pair of rabbits (one of each gender) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits on the island after n months, assuming that rabbits never die. This is the original problem considered by Leonardo Pisano (Fibonacci) in the thirteenth century. Rabbits and the Fiobonacci Numbers (cont.) Modeling the Population Growth of Rabbits on an Island Rabbits and the Fibonacci Numbers (cont.) Solution: Let fn be the the number of pairs of rabbits after n months. There are is f1 = 1 pairs of .

• Toán học
• Discrete mathematics
• Modeling computation
• Number theory
• Advanced counting techniques
• Advanced counting techniques
• Recurrence relations
• Solving linear recurrence relations
• Discrete mathematics applications
• Discrete Structures
• Mathematical Reasoning
• Discrete Probability
• Lecture Discrete Mathematics I
• Discrete Mathematics I
• Bài giảng Toán rời rạc
• Probability rules
• andom variables
• Probability models
• Combinatorial Analysis
• Computer Science
• Applications discrete mathematics
• The foundations
• Basic structures
• The integers