schrorer.html

Counting Principles

Jimmy Schroer

Counting procedures are an important area of mathematics that serves many "real world" purposes. From determining the odds of a straight in a poker hand to calculating the chance that a mass produced product will have a defect, counting procedures have a wide range of uses. This is a field of mathematics that continues to expand today, as some of the more complex principles are relatively new. Computers have contributed to this because mathematicians are now able to do more complex calculations. This worksheet is designed to explore the basics of counting principles and some of the uses of these principles. To gain the most from this worksheet, you are encouraged to read and understand all of the definitions given before working on the problems in that section.

Section 1: Sequential Counting

The Multiplication Principle for counting procedures is an important property. Mathematically speaking, if a procedure can be described as a sequence of n independent steps with possible outcomes for step 1, possible outcomes for step 2, and possible outcomes for step m, the total number of composite outcomes of the procedure is: ... where all i are multiplied together. What this basically says is that when an event can be subdivided into individual events in which each subdivided event is not effected by any other subdivided event, you can count the total number of outcomes by multiplying together the number of outcomes from each subdivided event. To count events in this way is called sequential counting. To further illustrate this, the following question gives an example of sequential counting using the multiplication principle.

Example: How many ways is there to answer a true-false test of four questions.

To answer this question, it must be divided up into individual events. We can address each question from the test individually since the answer on one question has no effect on the answer of another question. There are 2 ways to answer the first question (either true or false), 2 ways to answer the second, 2 ways to answer the third, and 2 ways to answer the fourth. If taken as separate events, these can be multiplied together to obtain the answer. The number of ways to answer a test like this is: 2*2*2*2 = = 16.

Section 2: Case by Case Counting

We have studied the multiplication principle and did some problems using that principle. Sometimes though we need to count things in a different manner. When the total number of possibilities of an event can be divided up into cases, then we can use the Addition Principle . The addition principle states that if a procedure can be divided into cases where each case presents a different outcome than every other case, the total number of outcomes is the addition of the number of outcomes for each case. Mathematically, if there are possible outcomes for the first event, possible outcomes for the second event, and possible outcomes for the nth event, then the total number of outcomes of the procedure is the sum + ... + . Here is an example exploring this type of counting.

Example: On a bookshelf there are 5 different calculus books, 6 different algebra books, and 7 different geometry books. In how many ways can a pair of books of different types be chosen?

To answer this question we can divide the possibilities into cases, count the number of ways in each case, and then use the addition principle to find the total. Case 1 will be the case where we choose one calculus book and one algebra book. There are 5 ways to choose the calculus book and 6 ways to choose the algebra book, so by the multiplication principle there are 5*6 or 30 ways to choose one calculus book and one algebra book. This is only one case. Case 2 is when we choose one algebra book and one geometry book. Using the same procedure as before, there are 6 ways to choose the algebra book and 7 ways to choose the geometry book, so there are 6*7 or 42 ways in case 2. Case 3 is when we choose one calculus book and one geometry book. There are 5 ways to choose a calculus book and 7 ways to choose a geometry book. So there are 5*7 or 35 ways in case 3. These are all of the possible cases, so to total them we can use the addition principle. This states that we can just add the total of each of the outcomes of the cases to determine the total number of outcomes. Adding, we get = 107. So there are 107 ways to select 2 books of different types from this shelf.

Section 3: Permutations

An arrangement of all the elements in a set into a sequence of length n is called a permutation . If objects are arranged in a certain order, permutations are used to determine how many arrangements of the objects that there are. The notation is where n is the number of elements of the set and k is the number of elements chosen from the set of n elements in the permutation. This number can be calculated using factorials. The factorial of a number is the number multiplied by each of the integers less than that number with the last number multiplied being 1. For example, 4! (! is the notation for factorial) = 4*3*2*1 = 24. is equal to . ( Why? And don't say 'because I said so'. ) The following example will help you understand this method of counting.

Example: How many permutations of length 2 are there out of the set of letters a, b, c, and d?

To answer this, we can apply two different methods. One is a direct method by writing down each possible permutation and counting the total. The options are: ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc. There are 12 of these. The other way to calculate this total is by the formula. We are looking for where n = 4 because there are 4 possible letters in the set and k = 2 because we are permuting two letters. = = = 12. We get the same answer using the permutation formula. When we cannot easily list all of the possible outcomes as we did at first in this problem, the permutation formula makes it possible for us to count permutations quickly and easily.

Section 4: Combinations

A combination is very similar to a permutation. In a permutation, the order of the elements matters (in our example, ab and ba are 2 distinct outcomes). In combinations, order does not matter. The symbol represents the number of combinations of k elements out of a set of n elements. = . Ouch! How are they supposed to know this? Derive this from the formula for p(n,k).

Example: How many combinations of length 2 are there out of the set of letters a, b, c, and d (order does not matter)? When order mattered, there were 12 different permutations. The possible combinations are: ab, ac, ad, bc, bd, and cd. There are 6 total. Using the combination formula:

= = = 6. Once again we get the same answer using the formula. When there are many possibilities for outcomes, the formula allows the calculations to be rather elementary.

Section 5: Probability

To define probability, we must define two other terms. Sample space , S, refers to the set of all possible outcomes. The event space , E, refers to some subset of S. Probability is defined as the likelihood of an event, or mathematically . This number is between 0 and 1 inclusive. The applications of probability calculations reach far beyond high school mathematics.

Example: A coin is flipped 4 times. What is the probability of the event where exactly 2 heads occur? To answer this question, we must first find S. S is the number of possible outcomes. With this problem we can use the multiplication principle. There are 2 possibilities for each of the 4 flips, so there are total possibilities (S = = 16). Now we must find E, or the number of possibilities where exactly 2 heads occur. We can do this by answering the question "how many ways can we choose 2 heads out of four flips?" This is simply = = 6. So in this problem E = 6. Now to find the probability, divide the size of S (16) by the size of E (6), or = .375. So, the chances of getting exactly two heads when flipping a coin four times is .375, or 37.5%.

Nice sequence of topics and nice treatment. (except for the authoritarian definition of C(n,r) and P(n,r))

Problems

Section 1 problems:

Problem 1: A liscense plate in Kentucky has 3 letters and 3 digits. How many possible liscense plates can Kentucky give out without giving out duplicate plates?

Problem 2: How many ways can one arrange 6 distinguishable books on a bookshelf?

Section 2 problems:

Problem 3: How many 4-digit integers are there that contain exactly one 8?

Problem 4: How many integers are there from 1 to 9999 that have distinct digits?

Section 3 problems:

Problem 5: How many 7-letter strings with no repeated letters can be formed?

Problem 6: A conference has nine speakers, five on how to use the internet and four on different types of computer programs. If each of the speakers about the internet have to go before the speakers on computer programs, how many different arrangements of speakers are there? (Hint: First arrange the internet speakers, then arrange the computer programs speakers)

Section 4 problems:

Problem 7: If there are 12 players on a basketball team, how many ways does the coach have to choose 5 of the players to start?

Problem 8: A juggling club has 17 members. In how many ways can a captain and 3 regular team members be choosen to form a team?

Section 5 problem:

Problem 9 (challenge problem): A poker hand consists of 5 cards out of 52 cards in a regular deck of playing cards. What is the probability of getting a full house (2 of one rank and 3 of another rank)?