This chapter extends your database design skills by presenting normalization techniques to remove redundancy in relational tables. In this chapter, you learned about the notation used in entity relationship diagrams, important data modeling patterns, guidelines to avoid common modeling errors, and conversion of entity relationship diagrams (ERDs) into relational tables. You applied this knowledge to construct ERDs for small, narrative problems. | (CSC 102) Lecture 27 Discrete Structures Counting Rules and Probability Previous Lecture Counting Elements Difference Rule Inclusion/Exclusion Rule Pigeon Hole Principle Generalized Pigeon Hole Principle Today’s Lecture Counting Elements of Disjoint Sets Counting the Number of Integers Relation between Permutations and Combinations Probability Axioms of Probability Expected Value Pigeon Hole Principle Selecting a Pair of Integers with a Certain Sum Let A = {1, 2, 3, 4, 5, 6, 7, 8}. a. If five integers are selected from A, must at least one pair of the integers have a sum of 9? b. If four integers are selected from A, must at least one pair of the integers have a sum of 9? Solution: a. Yes. Partition the set A into the following four disjoint subsets: {1, 8}, {2, 7}, {3, 6}, and {4, 5} Observe that each of the integers in A occurs in exactly one of the four subsets and that the sum of the integers in each subset is 9. Thus if five integers from A are chosen, then by the pigeonhole principle, two must be from the same subset. It follows that the sum of these two integers is 9. Cont More formally, by the pigeonhole principle, since P is not one-to-one, there are integers ai and aj such that P(ai ) = P(aj ) and ai = aj . But then, by definition of P, ai and aj belong to the same subset. Since the elements in each subset add up to 9, ai + aj = 9. Cont b. The answer is no. This is a case where the pigeonhole principle does not apply; the number of pigeons is not larger than the number of pigeonholes. For instance, if you select the numbers 1, 2, 3, and 4, then since the largest sum of any two of these numbers is 7, no two of them add up to 9. Generalized Pigeonhole Principle For any function f from a finite set X with n elements to a finite set Y with m elements and for any positive integer k, if k < n/m, then there is some y ∈ Y such that y is the image of at least k + 1 distinct elements of X. Applying the Generalized Pigeonhole Principle Show how the generalized . | (CSC 102) Lecture 27 Discrete Structures Counting Rules and Probability Previous Lecture Counting Elements Difference Rule Inclusion/Exclusion Rule Pigeon Hole Principle Generalized Pigeon Hole Principle Today’s Lecture Counting Elements of Disjoint Sets Counting the Number of Integers Relation between Permutations and Combinations Probability Axioms of Probability Expected Value Pigeon Hole Principle Selecting a Pair of Integers with a Certain Sum Let A = {1, 2, 3, 4, 5, 6, 7, 8}. a. If five integers are selected from A, must at least one pair of the integers have a sum of 9? b. If four integers are selected from A, must at least one pair of the integers have a sum of 9? Solution: a. Yes. Partition the set A into the following four disjoint subsets: {1, 8}, {2, 7}, {3, 6}, and {4, 5} Observe that each of the integers in A occurs in exactly one of the four subsets and that the sum of the integers in each subset is 9. Thus if five integers from A are chosen, then by the pigeonhole .
