tailieunhanh - Lecture Discrete structures: Chapter 26 - Amer Rasheed

This chapter provided a broad presentation about the database development process. You learned about the relationship between database development and information systems development, the phases of database development, and the kinds of skills you need to master. This chapter presents the notation of entity relationship diagrams to provide a foundation for using entity relationship diagrams in the database development process. | (CSC 102) Lecture 26 Discrete Structures Counting Rules II Previous Lecture Introduction Multiplication Rule Permutation Permutations of Objects Around a Circle Property of P(n, r) Today Lecture Counting Elements Difference Rule Inclusion/Exclusion Rule Pigeon Hole Principle Generalized Pigeon Hole Principle Permutations A permutation of a set of objects is an ordering of the objects in a row. For example, the set of elements a,b, and c has six permutations. abc, acb, cba, bac, bca, cab In general, given a set of n objects, how many permutations does the set have? Imagine forming a permutation as an n-step operation: Cont Permutations of Objects Around a Circle At a meeting of diplomats, the six participants are to be seated around a circular table. Since the table has no ends to confer particular status, it doesn’t matter who sits in which chair. But it does matter how the diplomats are seated relative to each other. In other words, two seating's are considered the same if one is a rotation of the other. How many different ways can the diplomats be seated? Solution: Call the diplomats by the letters A, B,C, D, E, and F. Since only relative position matters, you can start with any diplomat (say A), place that diplomat anywhere Cont and then consider all arrangements of the other diplomats around that one. B through F can be arranged in the seats around diplomat A in all possible orders. So there are 5! = 120 ways to seat the group. Permutations of Selected Elements Cont Evaluating r-Permutations a. Evaluate P(5,2). b. How many 4-permutations are there of a set of seven objects? c. How many 5-permutations are there of a set of five objects? Permutations of Selected Letters of a Word a. How many different ways can three of the letters of the word BYTES be chosen and written in a row? b. How many different ways can this be done if the first letter must be B? Cont Proving a Property of P(n, r) Prove that for all integers n ≥ 2, P(n,2) + P(n,1) = n2 Counting . | (CSC 102) Lecture 26 Discrete Structures Counting Rules II Previous Lecture Introduction Multiplication Rule Permutation Permutations of Objects Around a Circle Property of P(n, r) Today Lecture Counting Elements Difference Rule Inclusion/Exclusion Rule Pigeon Hole Principle Generalized Pigeon Hole Principle Permutations A permutation of a set of objects is an ordering of the objects in a row. For example, the set of elements a,b, and c has six permutations. abc, acb, cba, bac, bca, cab In general, given a set of n objects, how many permutations does the set have? Imagine forming a permutation as an n-step operation: Cont Permutations of Objects Around a Circle At a meeting of diplomats, the six participants are to be seated around a circular table. Since the table has no ends to confer particular status, it doesn’t matter who sits in which chair. But it does matter how the diplomats are seated relative to each other. In other words, two seating's are considered the same if one is a