tailieunhanh - Lecture Discrete structures: Chapter 25 - Amer Rasheed

In this chapter, the following content will be discussed: Relational DBMSs dominate the market for business DBMSs. You will undoubtedly use relational DBMSs throughout your career as an information systems professional. This chapter provides background so that you may become proficient in designing databases and developing applications for relational databases in later chapters. | (CSC 102) Lecture 25 Discrete Structures Counting Rules I Previous Lecture Principle of Mathematical Induction Proving Divisibility Property Proving an Inequality Proving Sequence Property Examples Strong Mathematical Induction Today’s Lecture Introduction Multiplication Rule Permutation Permutations of Objects Around a Circle Property of P(n, r) Introduction Teams A and B are to play each other repeatedly until one wins two games in a row or a total of three games. One way in which this tournament can be played is for A to win the first game, B to win the second, and A to win the third and fourth games. Denote this by writing A–B–A–A. How many ways can the tournament be played? Solution: The possible ways for the tournament to be played are represented by the distinct paths from “root” (the start) to “leaf” (a terminal point) in the tree, The label on each branching point indicates the winner of the game. The notations in parentheses indicate the winner of the tournament. Out come of the Tournament The fact that there are ten paths from the root of the tree to its leaves shows that there are ten possible ways for the tournament to be played. They are (moving from the top down): A–A, A–B–A–A, A–B–A–B–A, A–B–A–B–B, A–B–B, B–A–A, B–A–B–A–A, B–A–B–A–B, B–A–B–B, and B–B. In five cases A wins, and in the other five B wins. The least number of games that must be played to determine a winner is two, and the most that will need to be played is five. Out come of the Tournament Consider the following example. Suppose a computer installation has four input/output units (A, B,C, and D) and three central processing units (X, Y, and Z). Any input/output unit can be paired with any central processing unit. How many ways are there to pair an input/output unit with a central processing unit? To answer this question, imagine the pairing of the two types of units as a two-step operation: Step 1: Choose the input/output unit. Step 2: Choose the central processing unit. The possible . | (CSC 102) Lecture 25 Discrete Structures Counting Rules I Previous Lecture Principle of Mathematical Induction Proving Divisibility Property Proving an Inequality Proving Sequence Property Examples Strong Mathematical Induction Today’s Lecture Introduction Multiplication Rule Permutation Permutations of Objects Around a Circle Property of P(n, r) Introduction Teams A and B are to play each other repeatedly until one wins two games in a row or a total of three games. One way in which this tournament can be played is for A to win the first game, B to win the second, and A to win the third and fourth games. Denote this by writing A–B–A–A. How many ways can the tournament be played? Solution: The possible ways for the tournament to be played are represented by the distinct paths from “root” (the start) to “leaf” (a terminal point) in the tree, The label on each branching point indicates the winner of the game. The notations in parentheses indicate the winner of the tournament. Out come of