Fundamental Counting Principle

10 Key excerpts on "Fundamental Counting Principle"

• 

  eBook - PDF

  College Algebra

  • James Stewart, Lothar Redlin, Saleem Watson, , James Stewart, Lothar Redlin, Saleem Watson(Authors)
  • 2015(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  THE Fundamental Counting Principle Suppose that two events occur in order. If the first event can occur in m ways and the second can occur in n ways (after the first has occurred), then the two events can occur in order in m  n ways. There is an immediate consequence of this principle for any number of events: If E 1 , E 2 , . . . , E k are events that occur in order and if E 1 can occur in n 1 ways, E 2 in n 2 ways, and so on, then the events can occur in order in n 1  n 2  . . .  n k ways. EXAMPLE 1 ■ Using the Fundamental Counting Principle An ice-cream store offers three types of cones and 31 flavors. How many different single-scoop ice-cream cones is it possible to buy at this store? SOLUTION There are two stages for selecting an ice-cream cone. At the first stage we choose a type of cone, and at the second stage we choose a flavor. We can think of the different stages as boxes: Stage 1: Type of Cone Stage 2: Flavor Route q p x x y y z z px py pz qx qy qz A B B C C C C C C FIGURE 1 Tree diagram Copyright 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. SECTION 9.1 ■ Counting 649 The first box can be filled in three ways, and the second can be filled in 31 ways: Stage 1 Stage 2 3 31 By the Fundamental Counting Principle there are 3  31  93 ways of choosing a single-scoop ice-cream cone at this store. Now Try Exercise 17 ■ EXAMPLE 2 ■ Using the Fundamental Counting Principle In a certain state, automobile license plates display three letters followed by three dig-its.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Proofs and Ideas

  A Prelude to Advanced Mathematics

  • B. Sethuraman(Author)
  • 2021(Publication Date)
  • American Mathematical Society

    (Publisher)

  We can extract the arguments in these two examples and encode it into a simple principle: Definition 4.3. Fundamental Counting Principle (FCP): Suppose that Event ? 1 can be accomplished in ? 1 distinct ways, and for each way of accomplishing ? 1 , suppose that Event ? 2 can be accomplished in ? 2 distinct ways. Then the total number of ways in which ? 1 and ? 2 can be accomplished together is the product ? 1 ⋅ ? 2 . Remark 4.4 . The FCP can be extended to ? events using exactly the arguments we used in Examples 4.1 and 4.2. Suppose one has Events ? 1 , ? 2 , ... ? ? ( ? ≥ 1 ). Suppose that ? 1 can be accomplished in ? 1 distinct ways, and for each way of accomplishing ? 1 , ? 2 can be accomplished in ? 2 distinct ways, and for each way of accomplishing ? 1 and 4.1. Fundamental Counting Principle 51 ? 2 together, suppose that ? 3 can be accomplished in ? 3 distinct ways, and so on, then the total number of ways in which ? 1 , ? 2 , ... , ? ? can be accomplished together is the product ? 1 ⋅ ? 2 ⋅ ⋯ ⋅ ? ? . To illustrate the ideas that go into this, consider the same 7 cards in Example 4.2, but now consider the problem of forming three -letter words. Then if you pick ? the first time, you can pick any of ? , ? , ? , ? , ? or ? the second time, and therefore, with ? as the first choice, the six possible ways of picking the first two cards are (?, ?) , (?, ?) , (?, ?) , (?, ?) , (?, ?) , and (?, ?) (as in Example 4.2). But now for the third card: for each of these six possible ways of picking the first and second card, you have five choices for picking the third card, as there are now five cards left.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Algorithmic Mathematics

  • Stephen B. Maurer, Anthony Ralston(Authors)
  • 2005(Publication Date)
  • A K Peters/CRC Press

    (Publisher)

  CHAPTER 4 Fundamental Counting Methods 4.1 Introduction You have already had several occasions in this book to count things. Indeed, number is one of humanity’s fundamental concepts, and counting is one of the fundamental intellectual urges. Ever tried to count the stars in the sky or just the students in your math class? Ever wondered how many matching outfits you could put together from your wardrobe? We will concentrate in this chapter on how to count without worrying too much about what we count. We realize that this approach can be taken to an unfortunate extreme. Who cares how many ways a baseball manager can order nine players to form a lineup, or an anagrammist can rearrange the letters of “Mississippi”? The manager would never consider all possible lineups to be equally worthy, and the anagrammist would never need to know how many ways the reordering could take place. However, there is something to say for doing such “toy” examples. First, they are easy to state clearly and quickly, and so we can get on with the main business of learning solution methods. Second, they remind us that, in many situations where there is a lot of choice, the real issue is to find an optimal solution. Often the first step in solving optimization problems is to get an idea of how many choices there are. In an age of computers, if the number is not too large, brute force may be an effective algorithm find the best choice by trying them all. Even with an ingenious algorithm, we need to know how many steps the algorithm takes in order to know if it is fast enough for practical use. But determining the number of steps is just another counting problem. The subject of the analysis of algorithms is full of counting problems. We mentioned earlier that the hardest part of an analysis is often the average case analysis. Average case analysis uses probability, and for the most part probability computations of this sort consist of doing two counting problems and taking the ratio.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Combinatorics

  A Guided Tour

  • David R. Mazur(Author)
  • 2020(Publication Date)
  • American Mathematical Society

    (Publisher)

  C H A P T E R 1 Principles of Combinatorics Our journey begins with counting because combinatorics, in part, is the mathematics of counting. What does it mean to count? It means to determine the exact number of objects specified by a “How many?” question. What makes counting questions so appealing is that they arise in all sorts of settings, answering them builds your problem solving skills, and the answers are often fascinating in their sheer size. In this chapter we study the principles of counting that are foundational to combina-torics and that we will use in every other chapter. In the first two sections we practice classifying and solving basic counting questions. In the next two sections we study two principles (the bijection principle and the equivalence principle) that are useful for analyz-ing more difficult problems. In the last section, we introduce existence questions with the pigeonhole principle. Counting vs. enumerating We first make a note on the difference between counting and enumerating. One possible method of counting is to make a systematic and complete list of the objects being counted. This is called a complete enumeration or simply an enumeration . For example, if we wanted to know how many integers between 1 and 100 (inclusive) are divisible by 5 or 6, we could list them all: 5 6 10 12 15 18 20 24 25 30 35 36 40 42 45 48 50 54 55 60 65 66 70 72 75 78 80 84 85 90 95 96 100: There are 33. Complete enumeration is a viable counting technique for small problems but not for large ones. If we want to count the number of 9 STX 9 filled-in Sudoku boards 1 then we should not make a list because there are exactly 6;670;903;752;021;072;936;960 boards, about 6.6 sextillion. Even a computer that could generate 100 billion different Sudoku boards per second (exceedingly generous to the point of absurdity) would still take 1 Visit en.wikipedia.org/wiki/Sudoku if you somehow missed the Sudoku craze. 1

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Discrete Transition to Advanced Mathematics

  Second Edition

  • Bettina Richmond, Thomas Richmond(Authors)
  • 2023(Publication Date)
  • American Mathematical Society

    (Publisher)

  The number of outcomes for any sequence of tasks is the product of the numbers of outcomes for the individual tasks. If we have  tasks and the set of outcomes for the -th task is   , the outcomes for the sequence of tasks is {( 1 ,  2 , ...   ) ∣   ∈   } =  1 ×  2 × ⋯ ×   . Our extended version of the Fundamental Principle of Counting simply says | 1 ×  2 × ⋯ ×   | = | 1 | ⋅ | 2 | ⋯ |  |, as we saw in Theorem 1.2.9. For example, suppose a high school committee is to consist of one freshman, one sophomore, one junior, and one senior. If there are 135 freshmen, 156 sophomores, 123 juniors, and 127 seniors, then the number of ways we may choose the committee consisting of one representative from each class is (135)(156)(123)(127) = 328, 978, 260. Example 4.2.2. On a flight with 138 passengers, each passenger had the choice of pret- zels or cookies for a snack and the choice of chicken or pasta for dinner. The beverage service offered 12 beverages. A flight attendant remarked that no two passengers had the same request. Is this possible in the following scenarios: a) Each passenger took one snack, one dinner, and one beverage? b) Each passenger took no more than one selection from each category? c) The flight attendant, being a new recruit, offered the snack by asking “Pretzels, cookies, or both?”, and each passenger took no more than one dinner or beverage. Solution. First note that it is possible for all 138 passengers to make different requests only if there are 138 or more outcomes to the sequence of tasks of choosing a snack, dinner, and beverage.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Applied Combinatorics

  • Alan Tucker(Author)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  This text will try to give proper attention to asking the right questions as well as answering these questions. This section starts with two elementary but Fundamental Counting Principles whose simplicity masks both their power and the ease with which they can be misused. The Addition Principle If there are r 1 different objects in the first set, r 2 different objects in the second set, ... , and r m different objects in the mth set, and if the different sets are disjoint, then the number of ways to select an object from one of the m sets is r 1 + r 2 +···+ r m . The Multiplication Principle Suppose a procedure can be broken into m successive (ordered) stages, with r 1 different outcomes in the first stage, r 2 different outcomes in the second stage, ... , and r m different outcomes in the mth stage. If the number of outcomes at each stage is independent of the choices in previous stages and if the com- posite outcomes are all distinct, then the total procedure has r 1 × r 2 ×···× r m different composite outcomes. Remember that the addition principle requires disjoint sets of objects and the multiplication principle requires that the procedure break into ordered stages and that the composite outcomes be distinct. The validity of these two principles follows directly from the definitions of addition and multiplication of integers. That is, the sum a + b is the number of items resulting when a set of a items is added to a set of b items; and the product a × b is the number of sequences (A,B), when A can be any of a items and B can be any of b items. The two principles are standard mth-order extensions of these two binary operations. 5.1 Two Basic Counting Principles 181 Example 1: Rolling Dice Two dice are rolled, one green and one red.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  All the Math You Missed

  (But Need to Know for Graduate School)

  • Thomas A. Garrity(Author)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  18 Combinatorics and Probability Theory Basic Goals: Cleverly Counting Large Finite Sets Central Limit Theorem Beginning probability theory is basically the study of how to count large finite sets, or in other words, an application of combinatorics. Thus the first section of this chapter deals with basic combinatorics. The next three sections deal with the basics of probability theory. Unfortunately, counting will only take us so far in probability. If we want to see what happens as we, for example, play a game over and over again, methods of calculus become important. We concentrate on the Central Limit Theorem, which is where the famed Gauss bell curve appears. The proof of the Central Limit Theorem is full of clever estimates and algebraic tricks. We include this proof not only because of the importance of the Central Limit Theorem but also to show people that these types of estimates and tricks are sometimes needed in mathematics. 18.1 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . There are many ways to count. The most naive method, the one we learn as children, is simply to explicitly count the elements in a set, and this method is indeed the best one for small sets. Unfortunately, many sets are just too large for anyone to merely count the elements. Certainly in large part the fascination in card games such as poker and bridge is that while there are only a finite number of possible hands, the actual number is far too large for anyone to deal with directly, forcing the players to develop strategies and various heuristical devices. Combinatorics is the study of how to cleverly count. Be warned that the subject can quickly get quite difficult and is becoming increasingly important in mathematics. We will look at the simplest of combinatorial formulas, ones that have been known for centuries.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Mathematical Excursions

  • Richard Aufmann, Joanne Lockwood, Richard Nation, Daniel K. Clegg(Authors)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Solving this problem is critical to enabling computers to interpret human speech. MATH MATTERS A standard deck of playing cards Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 700 CHAPTER 12 | Combinatorics and Probability Applying Several Counting Techniques The permutation formula is derived from the counting principle. This formula is a conve- nient way of expressing the number of ways in which the items in an ordered list can be arranged. Both the permutation formula and the counting principle are needed to solve some counting problems. EXAMPLE 4 Counting Using Several Methods Five women and four men are to be seated in a row of nine chairs. How many different seating arrangements are possible if a. there are no restrictions on the seating arrangements? b. the women sit together and the men sit together? Solution Because seating arrangements have a definite order, they are permutations. a. If there are no restrictions on the seating arrangements, then the number of seating arrangements is P( 9, 9). P( 9, 9) = 9! ( 9 − 9)! = 9! 0! = 9! = 362,880 There are 362,880 seating arrangements. b. This is a multi-stage experiment, so both the permutation formula and the counting principle will be used. There are 5! ways to arrange the women and 4! ways to arrange the men. We must also consider that either the women or the men could be seated at the beginning of the row. There are two ways to do this. By the counting principle, there are 2 ? 5! ? 4! ways to seat the women together and the men together.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  An Invitation to Combinatorics

  • Shahriar Shahriari(Author)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  Proposition 3.6 (Subtraction Principle). Let A be a subset of a set S, and denote the complement of A in S by A c . Then |A| = |S| −   A c   . Basically, all we are saying is that sometimes it is easier to count the objects that we don’t want. Example 3.7. How many integers n with 1 ≤ n ≤ 1500 have at least two distinct digits? Solution. There are a total of 1500 integers between 1 and 1500. How many of them don’t have at least two distinct digits? The 9 one-digit numbers, 9 of the two-digit numbers (namely, 11, 22, . . . , 99), 9 of the three-digit numbers (namely, 111, 222, . . . , 999), and 1 of the four- digit numbers (namely, 1111). Hence, the total number of integers between 1 and 1500 that have at least two distinct digits is 1500 − (9 + 9 + 9 + 1) = 1, 472.  Remark 3.8 (Double Counting as the Division Principle). Say you have a simple graph with five vertices and you know that the degrees of these vertices are 4, 3, 2, 2, and 1. These are the numbers of edges incident with each vertex, and if we add them we get 12. We can then argue that each edge of the graph is counted twice (once for each of its vertices), and so the 86 Counting, Probability, Balls and Boxes number of edges of the graph is 12/2 = 6. This is a simple example of counting something (in this case the number of edges of a graph) by first double counting (i.e., counting all the objects that we are interested in twice) and then dividing by 2. As such, you can think of the use of double counting (or triple counting, or …, or k-fold counting) as a kind of division principle for counting. Such a labeling, however, does not help in solving problems. We will get plenty of practice in the upcoming chapters. Remark 3.9. The addition, subtraction, and multiplication principles are pretty straightfor- ward ideas, and, most of the time, we use them without explicitly mentioning them. Even though the principles themselves are not that profound, it is quite possible to use them incorrectly.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  GRE All the Quant

  Effective Strategies & Practice from 99th Percentile Instructors

  • (Author)
  • 2023(Publication Date)
  • Manhattan Prep

    (Publisher)

  CHAPTER 29 Combinatorics

  Many GRE problems are, ultimately, just about counting things. Although counting may seem to be a simple concept, problems about counting can be complex. In fact, counting problems are a whole subfield of mathematics: combinatorics, which is essentially advanced counting. In combinatorics, you are often counting the number of possibilities. In this chapter, you will learn the fundamentals of combinatorics as tested on the GRE.

  You’ll also learn how to tackle more advanced counting problems. Here are some examples of the kinds of questions you may see:

  • A restaurant menu features 5 appetizers, 6 main dishes, and 3 desserts. If a dinner special consists of 1 appetizer, 1 main dish, and 1 dessert, how many different dinner specials are possible?
  • Four people sit down in 4 fixed chairs lined up in a row. How many different seating arrangements are possible?
  • If there are 7 people in a room, but only 3 chairs in a row, how many different seating arrangements are possible?
  • If a group of 3 people is to be chosen from 7 people in a room, how many different groups are possible?

  The Fundamental Counting Principle

  Counting problems commonly feature multiple separate choices. Whether such choices are made simultaneously (e.g., choosing types of bread and filling for a sandwich) or sequentially (e.g., choosing among routes between successive towns on a road trip), the rule for counting the number of options is the same.

  Key Concept

  Fundamental Counting Principle: When making a number of separate decisions, multiply the numbers of ways to make each individual decision to find the total number of ways to make all the decisions.

  Imagine that you are making a sandwich. You’ll choose one type of bread out of 2 types (rye or whole wheat) and one type of filling out of 3 types (chicken salad, peanut butter, or tuna fish). How many different kinds of sandwich can you make?

  Sign up to read

  Learn more about book