Counting Rules - JustAnswer



Counting RulesBasic Counting PrinciplesFirst of all, we introduce some basic techniques of counting. These methods serve as the foundation for almost all counting techniques.We present two basic counting principles: the product rule and the sum rule.Product RuleThe product rule applies when a procedure is made up of separate tasks.The product rule: Suppose that a procedure can be broken into a sequence of two tasks. If there are n1 ways to do the first task, and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1*n2 ways to do the procedure.Example 1: Suppose you toss two coins. What is the number of possible outcomes?Solution: The procedure of tossing two coins consists of two tasks, namely, tossing the first coin, then tossing the second coin. Tossing the first coin has two outcomes: head or tail. Tossing the second coin has two outcomes: head and tail. The product rule shows that there are 2 * 2 = 4 outcomes. These outcomes are:?The first coinThe second coin1HeadHead2HeadTail3TailHead4TailTailExample 2: Suppose you toss one fair dice and one coin. What is the number of possible outcomes?Solution: The procedure of tossing one dice and one coin consists of two tasks, namely, tossing the dice, then tossing the coin. Tossing the dice has six outcomes. Tossing the coin has two outcomes. The product rule shows that there are 6 * 2 = 12 outcomes. These outcomes are:Example 2: Suppose you toss one fair dice and one coin. What is the number of possible outcomes?Solution: The procedure of tossing one dice and one coin consists of two tasks, namely, tossing the dice, then tossing the coin. Tossing the dice has six outcomes. Tossing the coin has two outcomes. The product rule shows that there are 6 * 2 = 12 outcomes. These outcomes are:?The diceThe coin11Head21Tail32Head42Tail53Head63Tail74Head84Tail95Head105Tail116Head126TailExample 3: The chairs of auditorium are to be labeled with a letter of the alphabet and a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently?Solution: The procedure of labeling a chair consists of two tasks, namely, assigning one of the 26 letters, and then assigning one of the 100 possible integers to the seat. Assigning a letter has 26 outcomes. Assigning a number has 100 outcomes. The product rule shows that there are 26 * 100 = 2600 different ways that a chair can be labeled. Therefore, the largest number of chairs that can be labeled differently is 2600.An extended version of the product rule is often useful. Suppose that a procedure is carried out by performing the tasks T1, T2, …, Tm in sequence. If each task Ti, i=1,2,3…,m, can be done in ni ways, then there are n1*n2*n3*…*nm ways to carry out the procedure.Example 4: How many different license plates are available if each plate contains a sequence of three letters followed by three digits?Solution: There are 26 choices for each of the three letters and ten choices for each of the three digits. Hence, by the product rule, there are a total of 26 * 26 * 26 * 10 * 10 * 10 = 17,576,000 possible license plates.Example 5: A person can purchase a condominium with a choice of five kinds of carpeting, with or without a pool, with or without a porch, and with one, two, or three bedrooms. How many different options are there for the condominium?Solution: For the first choice, the carpeting, there are 5 options available. The second choice, the pool, there are just 2 options available. The third choice, the porch. Again, there are only 2 options available, with or without a porch. The product rule states that we should take the product of all these choices so there are different options for the condominium.Example 6: A store manager wishes to display 8 different brands of shampoo in a row. In how many different ways can this be done?Solution:87654321From left to right, for the first bottle of shampoo you have, of course, 8 different choices available. After putting one bottle on the shelf, you have 7 different brands left to put next to the first one. Likewise, you will have 6 bottles available to put in the third position. And this goes on until you have completed the alignment of 8 bottles of shampoo. The fundamental counting principle states that you can arrange the shampoos in different ways.Example 7: The call letters of a radio station must have 4 letters. The first letter must be a K or a W. How many different station calls can be made if repetitions are not allowed?Solution:2252423For the first letter of the station call you have only 2 options. It must be a K or a W. Since repetitions are not allowed you cannot use the first letter, either the K or the W, for any other letter in the station call. After choosing the first letter you now have 25 letters left to choose from. After selecting a letter as the second letter in the station call, which is different from the fist letter you chose, there are only 24 different letters left for the third letter and 23 for the fourth letter in the station call. The fundamental counting principle states that there are different station calls which can be made if repetitions are not allowed.Sum RuleThe sum rule: If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1+n2 ways to do the task.Example 8: Suppose that either a member of the computer science faculty or a student who is a computer major is chosen as a representative to a university committee. How many different choices are there for this representative if there are 37 members of the computer science faculty and 83 computer science majors and no one is both a faculty member and a student?Solution: There are 37 ways to choose a member of the computer science faculty and there are 83 ways to choose a student who is a computer science major. Choosing a member of the computer science faculty is never the same as choosing a student who is a computer science major because no one is both a faculty member and a student. By the sum rule, it follows that there are 37+83 = 120 possible ways to pick this representative.Example 9: There are 20 art majors and 50 CS majors. No students are double major. How many ways are there to pick one art major or one CS major?Solution: There are 20 ways to choose an art major and there are 50 ways to choose a CS major. Choosing an art major is never the same as choosing a CS major because no one is double major. By the sum rule, it follows that there are 20+50 = 70 possible ways.To learn more about basic counting rules, check the following sites:The Basic Rules of Counting ( HYPERLINK "" \t "_blank" )Introduction to Counting ( HYPERLINK "" \t "_blank" )Assignment1. The format of telephone numbers in North America is specified by a numbering plan. Atelephone number consists of 10 digits, which are split into a three-digit area code, athree-digit office code, and a four-digit station code.Because of signaling considerations, there are certain restrictions on some of these digits.To specify the allowable format, let X denote a digit that can take any of the value 0through 9, let N denote a digit that can take any values 2 through 9.In the numbering plan, the formats of the area, office and station codes are:Area code: NXXOffice code: NXXStation code: XXXXa) How many different area codes are there?b) How many different office codes are there?c) How many different station codes are there?2. A student can choose a computer project from one of three lists. The three lists contain23, 15, and 19 possible projects, respectively. No project is on more than one list. Howmany possible projects are there to choose from?Please respond to both questions.A machine shop has eight screw machines but only three spaces available in the production area for the machine. In how many different ways can the eight machines be arranged in the three spaces available?A quality control randomly selects two of five parts to test for defects. In a group of five parts, how many combinations of two parts can be selected?Counting RulesComplex Counting ProblemMany counting problems cannot be solved using just the sum rule or just the product rule. However, many complicated counting problems can be solved using both of these rules in combination.Example 10: Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or a digit. How many possible passwords are there?Solution: Let P be the total number of possible passwords, and P(6), P(7) and P(8) denote the number of possible passwords of length 6, 7, and 8. By the sum rule, P = P(6)+P(7)+p(8).Now we need to find P(6), P(7), and P(8).For a password of 6 characters long, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(6) = 36*36*36*36*36*36=2,176,782,336For a password of 7 characters long, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(7) = 36*36*36*36*36*36*36=78,364164,096For a password of 8 characters long, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(8) = 36*36*36*36*36*36*36*36=2,821,109,907,456So P=P(6)+P(7)+P(8)=2,901,650,853,888Example 11: Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or a digit. The first character must be a letter, not a digit. How many possible passwords are there?Solution: This example is the same as the Example 10 except there is one restriction “The first character must be a letter, not a digit”.Let P be the total number of possible passwords, and P(6), P(7) and P(8) denote the number of possible passwords of length 6, 7, and 8. By the sum rule, P = P(6)+P(7)+p(8).Now we need to find P(6), P(7), and P(8).For a password of 6 characters long, there are 26 choices for the first character (26 letters), all the other five characters, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(6) = 26*36*36*36*36*36=1,572,120,576For a password of 7 characters long, there are 26 choices for the first character (26 letters), all the other six characters, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(7) = 26*36*36*36*36*36*36=56,596,340,736For a password of 8 characters long, there are 26 choices for the first character (26 letters), all the other seven characters, there are 36 choices (26 letters + 10 digits = 36) for each character, so P(8) = 26*36*36*36*36*36*36*36=2,037,468,266,496So P=P(6)+P(7)+P(8)=2,095,636,727,808To learn more about set operations, check the following sites:Basic Counting Rules (Page 1) ( HYPERLINK "" \t "_blank" )Counting (Pages 1-3) ( HYPERLINK "" \t "_blank" )Assignment1. Assume a computer system requires that the length of the passwords is 1, 2, 3, or 4. Andthe passwords consist of lowercase letters. How many passwords are there?2. Assume a computer system requires that the length of the passwords is 1, 2, 3, 4, or 5.And the passwords consist of digits (0 to 9). How many passwords are there?Graph Models and Graph TheoryBasic Graph ConceptsVew a presentation about basic HYPERLINK "" \t "_blank" graph terminology.To learn more about graphs, check the following sites:Graphs and Graph Theory ( HYPERLINK "" \t "_blank" )Graph theory ( HYPERLINK "" \t "_blank" )AssignmentGiven the following graph, 1. fill out the table belowPropertyValues:Set of VerticesThe size of the graphDegree of the Vertex 1Degree of the Vertex 3Show one path from 1 to 6Are 2 and 4 adjacent?Is this a complete graph?Describe the concept of a complete graph? Provide an example of a four-vertex graph for your classmates to solve for an adjacency list. Graph Models and Graph TheoryBipartite Graph and Graph RepresentationView a? HYPERLINK "" \t "_blank" presentation on bipartite graphs and the representation of graphs by an adjacency list.To learn more about bipartite graphs and graph representations, check the following sites:Bipartite Graph ( HYPERLINK "" \t "_blank" )Adjacency List ( HYPERLINK "" \t "_blank" )AssignmentGiven the following grapha) Is this graph a binary graph?b) Represent this graph using an adjacency matrix.c) Represent this graph using an adjacency list. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download