1 Exponents (Section P.2 , page 20)
2 Factorials (Section 8.1 , page 721)
Social Security numbers may seem to be assigned randomly, but they are not. Although the details are complicated, here is a brief introduction: First, the format for all Social Security numbers is NNN-NN-NNNN, where N must be one of the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. U.S. citizens, permanent residents, and certain temporary residents are issued these numbers. For working people, the numbers help track tax contributions and Social Security benefits.
The first three digits in a Social Security number make up an area number assigned to a geographic location. The area number indicates the state in which the card was issued or the ZIP Code in the mailing address provided in the original application.
The middle two digits constitute a group number and are designed simply to break the Social Security number into convenient blocks for issuance. The exact procedure is not very enlightening.
The last four digits are serial numbers and are assigned in each group from 0001 through 9999.
Various restrictions limit the numbers that can be used. For example, numbers with all zeros in any of the digit blocks (000-xx-xxxx, xxx-00-xxxx, or xxx-xx-0000) are never issued. Even if there were no restrictions, at some point, there might be more people than available numbers. How many numbers can be issued in the Social Security format with no restrictions? The answer is 1,000,000,000 (1 billion). (The U.S. population in January 2013 was about 315,000,000 [315 million].)
In Example 3, you learn how to calculate the total number of possible Social Security numbers.
1 Use the Fundamental Counting Principle.
You may think that you already know all there is to know about counting. However, mathematicians have developed a variety of techniques that allow you to determine the number of items that are of interest to you without making the effort of listing and counting all of them. We start with an example that easily lists the items to be counted, but that also demonstrates a general counting procedure.
Suppose you are trying to decide between buying a sport-utility vehicle (SUV) and a four-door sedan. The SUV is available in black, red, and silver. The sedan is available in black, blue, and green. In how many ways can you choose a type of car and its color?
We can represent the possible solutions by using a tree diagram, as shown in Figure 8.7. There are two initial choices: an SUV and a sedan. For each of these two choices, there are three additional choices of color; so a total of 2⋅3=6
Construct a tree diagram and determine the number of ways you can choose to take one of three courses—English, French, or Math—in the morning, afternoon, or evening.
The car selection process in Example 1 involves making two choices. First, choose a type of car; second, choose a color. It is important in this process that the same number of choices be available for the second choice regardless of the result of the first choice. The exact rules for counting by this method are given next.
A disc jockey wants to open a program by picking a song from among 40 songs by one artist and close the program by picking a song from among 32 songs by a second artist. How many different choices are possible?
Each choice of an opening and ending song sequence can be obtained as follows:
First, choose an opening song in 40 ways.
Second, choose the song to end the program in 32 ways.
Because no matter which song is chosen to open the program, all 32 songs are available to end the program, the counting principle applies, and there are a total of
possible choices for the opening and ending sequences.
Reba gets to choose both dinner and a movie for a Saturday night date. She can choose from any of seven restaurants and five movies. How many different choices are possible?
Be careful when using the Fundamental Counting Principle. Suppose you are trying to decide between buying an SUV available only in black, red, or silver and a convertible available only in black or red. In how many ways can you choose a type of car and its color? The car and color can be selected by making two choices: type (SUV or convertible) followed by color. But in this situation, the number of ways you can make the second choice depends on the first choice. You can choose from three colors for an SUV, but only two colors for a convertible. The Fundamental Counting Principle does not apply. Fortunately, there are so few different choices here that you can easily list all five: black SUV, red SUV, silver SUV, black convertible, and red convertible.
Social Security numbers have the format NNN-NN-NNNN, where each N must be one of the integers 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Assuming that there are no other restrictions, how many such numbers are possible?
There are nine positions in the format
Because the number of choices available at each position is not affected by previous choices, the Fundamental Counting Principle can be used. Replace each of the letters N with a blank to be filled in with one of the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
We have
Thus, there are 109=1,000,000,000
In Example 3 , suppose we fix the area number for the Social Security number to be 433. How many social security numbers can be assigned to this area—that is, numbers having the form 433-NN-NNNN?
2 Use the formula for permutations.
How many different ways can five people be arranged in a row for a group photograph?
To count the number of ways we can arrange five people in a row for a group photograph, we can assign numbers to each of the five photograph positions.
Then we proceed as follows:
First, choosing any of the five people for Position 1 gives 5 ways.
Second, choosing one of the four remaining people for Position 2 gives 4 ways.
Third, choosing one of the three remaining people for Position 3 gives 3 ways.
Fourth, choosing one of the remaining two people for Position 4 gives 2 ways.
Fifth, choosing the last person remaining for Position 5 gives 1 way.
Using the Fundamental Counting Principle, we see that there are
possible arrangements.
How many different ways can seven books be arranged on a shelf?
This technique gives a general formula for counting permutations of n distinct objects.
Sometimes only some, but not all, of the available objects are to be arranged in a specific order, again with no object being used more than once. You may want to choose r objects from among n available objects. This type of ordering is called a permutation of n objects taken r at a time.
Three prizes (for first, second, and third place) are to be given out in a dog show having 27 contestants. In how many different ways can dogs come in first, second, and third?
Consider how we might list the prize winners:
Any dog might win first prize; there are 27 possibilities.
Any remaining dog might win second prize; there are 26 possibilities.
Any remaining dog might win third prize; there are 25 possibilities. We can use the Fundamental Counting Principle: there are
distinct ways that the dogs can come in first, second, and third. This is an example of permutations of 27 objects taken 3 at a time.
There are nine different rides at a state fair. A group has to decide which four rides they will go on and in what order. How many possibilities are there?
Use the formula for P(n, r) to evaluate each expression.
P(7, 3)
P(6, 0)
P(7, 3)=7!(7−3!)Replace n with 7 and r with 3 in P(n, r).=7!4!=7⋅6⋅5⋅4!4!=7⋅6⋅5=210
P(6, 0)=6!(6−0)!Replace n with 6 and r with 0 in P(n, r).=6!6!=1
Evaluate.
P(9, 2)
P(n, 0)
Let’s apply the permutations formula to the problem of counting prizewinners in Example 5. The number of permutations of 27 dogs taken 3 at a time is
This is the same answer we found in Example 5.
3 Use the formula for combinations.
Order is not always important in selecting objects. For example, if someone is bringing six movies on a vacation, the order in which the movies were chosen is unimportant.
List all of the combinations of the four mascot names “bears,” “bulls,” “lions,” and “tigers,” taken two at a time. Find C(4, 2).
If “bears” is one of the mascots chosen, the possibilities are {bears, bulls}, {bears, lions}, and {bears, tigers}.
If “bulls” is one of the mascots chosen, the remaining possibilities (excluding {bears, bulls}) are {bulls, lions} and {bulls, tigers}.
The final choice of two mascot names is {lions, tigers}.
The combinations of the four mascot names taken two at a time are {bears, bulls}, {bears, lions}, {bears, tigers}, {bulls, lions}, {bulls, tigers}, and {lions, tigers}.
Because there are six such combinations, we have C(4, 2)=6.
List all of the combinations of the four mascot names “bears,” “bulls,” “lions,” and “tigers,” taken three at a time. Find C(4, 3).
To find a formula for C(n, r), we begin by comparing C(n, r) with P(n, r), the number of permutations of n objects taken r at a time. Suppose, for example, we have seven distinct objects—A, B, C, D, E, F, and G—and we pick three of them—A, D, and E (a combination of seven objects taken three at a time). This one combination ADE gives 3!=6
A similar process leads to a more general formula.
Use the formula C(n, r) to evaluate each expression.
C(7, 5)
C(8, 0)
C(4, 4)
C(7, 5)=7!(7 − 5)! 5! Replace n with 7 and r with 5 in C(n, r).=7!2! 5!=7⋅36⋅5!2⋅1⋅5!=21
C(8, 0)=8!(8 − 0)! 0!Substitute n=8 and r=0 in C(n, r).=8!8! 0!=1
C(4, 4)=4!(4 − 4)! 4!Substitute n=4 and r=4 in C(n, r).=4!4! 4!=1
Evaluate.
C(9, 2)
C(n, 0)
C(n, n)
How many different ways can five pizza toppings be chosen from the following choices: pepperoni, onions, mushrooms, green peppers, olives, tomatoes, mozzarella, and anchovies?
Eight toppings are listed, so the question is, in how many ways can we pick five things from a collection of eight things? That is, we need to find the number of combinations of eight objects taken five at a time, or C(8, 5).
Use the formula C(n,r)=n!(n−r)! r!.
There are 56 ways that five of the eight pizza toppings can be chosen.
A box of assorted chocolates contains 12 different kinds of chocolates. In how many ways can three chocolates be chosen?
4 Use the formula for distinguishable permutations.
Suppose you were to stand in a line with identical twins. Although the three of you can arrange yourselves in 3!=6
Front View of Tiles | Back View of Tiles |
---|---|
1 2 3 | M O M |
1 3 2 | M M O |
2 1 3 | O M M |
2 3 1 | O M M |
3 1 2 | M M O |
3 2 1 | M O M |
There are 3!=6
Now consider the corresponding arrangements of the letters M, O, and M on the back view of the tiles as the front view of the tiles are arranged to show each of the six permutations of 1, 2, 3. (See margin.)
There are only three distinguishable arrangements that appear when the tiles are viewed from the back: MOM, MMO, and OMM.
The front view shows the permutations of three distinct objects, but the back view shows the permutations of three objects of which one is of one kind (the letter O) and two are of a second kind (the letter M).
In how many ways can nine gifts be distributed among three children if each child receives three gifts?
If we number the gifts 1 through 9 and use A, B, and C to represent the children, we can visualize any distribution of gifts as an arrangement of the letters A, B, and C (each letter being used three times) above the numbers 1 through 9. Here is one possible arrangement:
In this arrangement, child A gets gifts 2, 3, and 7; child B gets gifts 1, 6, and 9; and child C gets gifts 4, 5, and 8.
To count all of the possible distributions of gifts, we count the number of permutations of nine objects, of which three are of one kind, three are of a second kind, and three are of a third kind:
There are 1680 ways the nine gifts can be distributed among the three children.
In how many ways can six counselors be sent in pairs to three different locations?
Suppose 23 students show up late for a private screening of a new movie. Suppose also that there is one seat available in each of the first, second, eighth, and tenth rows and that five students will be allowed to stand in the back of the theater.
Notice that
Because the Fundamental Counting Principle is used to count permutations, you can always use that principle instead of the formula for permutations.
There are frequently equally good, although different, ways to use counting techniques to solve a problem. For example, we could first choose 5 students to stand in the back of the theater in C(23, 5) ways and then assign the seats in rows 1, 2, 8, and 10 to the 18 remaining students in 18⋅17⋅16⋅15
Any arrangement of n distinct objects in a fixed order in which no object is used more than once is called .
The number of permutations of five distinct objects is .
When r objects are chosen from n distinct objects, the set of r objects is called a(n) of n objects taken r at a time.
The number of distinguishable permutations of 10 objects of which 3 are of one kind and 7 are of a second kind is .
True or False. When order is important in counting objects, we use permutations.
True or False. There are more permutations of n objects taken r at a time than there are combinations of n objects taken r at a time.
True or False. The number of distinguishable ways that 3 Coke, 2 Sprite, and 3 Pepsi cans can be arranged in a row is 56.
True or False. The number of ways a 5-person committee can be selected from 12 people is 5!
In Exercises 9–16, use the formula for P(n, r) to evaluate each expression.
P(6, 1)
P(7, 3)
P(8, 2)
P(10, 6)
P(9, 9)
P(5, 5)
P(7, 0)
P(4, 0)
In Exercises 17–24, use the formula for C(n, r) to evaluate each expression.
C(8, 3)
C(7, 2)
C(9, 4)
C(10, 5)
C(5, 5)
C(6, 6)
C(3, 0)
C(5, 0)
In Exercises 25–28, use the Fundamental Counting Principle to solve each problem.
How many different two-letter codes can be made from the 26 capital letters of the alphabet if (a) repeated letters are allowed; (b) repeated letters are not allowed.
How many possible answer sheets are there for a ten-question true–false exam if no answer is left blank?
In how many ways can a president and vice president be chosen from an organization with 50 members?
How many four-digit numbers can be formed with the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 if the first digit cannot be 0?
In Exercises 29–32, use the formula for counting permutations to solve each problem.
In how many different ways can the members of a family of four be seated in a row of four chairs?
Ten teams are entered in a bowling tournament. In how many ways can first, second, and third prizes be awarded?
Frederico has five shirts, three pairs of pants, and four ties that are appropriate for an interview. If he wears one of each type of apparel, how many different outfits can he wear?
A choreographer has to arrange eight pieces for a dance program. In how many ways can this be done?
In Exercises 33–36, use the formula for counting combinations to solve each problem.
A pizza menu offers pepperoni, peppers, mushrooms, sausage, and meatballs as extra toppings that can be added to your pizza. How many different pizzas can you order with two additional toppings?
In how many ways can 2 student representatives be chosen from a class of 15 students?
Students are allowed to choose 9 out of 11 problems to work for credit on an exam. How many ways can this be done?
You have to choose 3 out of 18 potential teammates to help you with a group assignment. How many ways can this be done?
In Exercises 37–42, solve the problem by any appropriate counting method.
How many ways can Ashley choose 4 out of 11 different canned goods to donate to charity?
How many ways can a computer store hire a salesclerk and a technician from seven applicants for the clerk position and four applicants for the technician position?
How many ways can six people be seated in a row with eight seats, leaving two seats vacant?
Seven students arrive to rent two canoes and three kayaks. How many ways can two students be selected to rent the canoes and three to rent the kayaks?
Dakota is trying to decide in which order to visit five prospective colleges. How many ways can this be done?
How many ways can the first 4 numbers be called from the 75 possible bingo numbers?
Area codes. How many three-digit area codes for telephones are possible if
The first digit cannot be a 0 or 1 and the second digit must be a 0 or 1?
There are no restrictions on the second digit? (Previous restrictions were abandoned in 1995.)
Radio station call letters. Radio stations in the United States have call letters that begin with either K or W (for example, WXYZ in Detroit). Some have a total of three letters, and others have four. How many different call-letter selections are possible?
Fraternity letters. The Greek alphabet contains 24 letters. How many three-letter fraternity names can be made with Greek letters
If no repetitions are allowed?
If repetitions are allowed?
Codes. How many three-letter codes can be made from the first ten letters of the alphabet if
No letters are repeated?
Letters may be repeated?
Supreme Court decisions. In how many ways can all of the nine justices of the U.S. Supreme Court reach a majority decision? (The U.S. Supreme Court has nine justices who are appointed for life.)
Committee selection. A club consists of ten members. How many ways can a committee of four be selected?
Wardrobe choices. Al’s wardrobe consists of eight pairs of slacks, eight shirts, and eight pairs of shoes. He does not want to wear the same outfit on any two days of the year. Will his current wardrobe allow him to do this?
Menu selection. A French restaurant offers two choices of soup, three of salad, eight of an entree, and five of a dessert. How many different complete dinners can you order?
Housing development. A developer wants to build seven houses, each of a different design. How many ways can she arrange these homes on a street if
Four lots are on one side of the street and three are on the opposite side?
Five lots are on one side of the street and two are on the opposite side?
Designing exercise sets. The author of a mathematics textbook has seven problems for an exercise set, and she is trying to arrange them in increasing order of difficulty. How many ways can she select the problems if no two of them are equally difficult? How many ways can the author fail?
Letter selection. From the letters of the word CHARITY, groups of four letters are formed (without regard to order). How many of them will contain
Both A and R?
A but not R?
Neither A nor R?
Committee selection. How many ways can a committee of 4 students and 2 professors be formed from 20 students and 8 professors?
Inventory orders. A manufacturer makes shirts in five different colors, seven different neck sizes, and three different sleeve lengths. How many shirts should a department store order to have one of each type?
International book codes. All recent books are identified by their International Standard Book Number (ISBN), a ten-digit code assigned by the publisher. A typical ISBN is 0-321-75526-2. The first digit, 0, represents the language of the book (English); the second block of digits, 321, represents the publishing company (Pearson); the third block of digits, 75526, is the number assigned by the publishing company to that book; and the final digit, 2, is the check digit, used to detect the most commonly made errors when ISBNs are copied. How many ISBNs are possible? (Remember that the previous nine digits determine the last digit.)
Political polling. A senator sends out questionnaires asking his constituents to rank ten issues of concern to them, such as crime, education, and taxes, in order of importance. Replies are filed in folders, and two or more replies are put in the same folder if and only if they give the same ranking to all ten issues. Find the maximum number of folders that might be needed.
Parcel delivery. A UPS driver must deliver 12 parcels to 12 different addresses. In how many orders can the driver make these deliveries?
Circus visit. A father with seven children takes four of them at a time to a circus as often as he can, without taking the same four children more than once. What is the maximum number of times each child will go to the circus, and how many times will the father go?
Arranging books. From six history books, four biology books, and five economics books, how many ways can a person select three history books, two biology books, and four economics books and arrange them on a shelf?
Bingo. Each of four columns on a bingo card contains 5 different numbers chosen in any order from 15. Column “B” chooses from 1 to 15, column “I” from 16 to 30, …, and column “O” from 61 to 75. Only four numbers are under column “N” because of the free space. How many different cards are possible?
Football conferences. The Grid-Iron Football League in Sardonia is divided into two conferences—East and West—each having six members. Each team in the league must play each team in its conference twice and each team in the other conference once during a season. What is the total number of games played in the league?
Married couples prohibited. How many ways can a committee of four people be selected from five married couples if no committee is to include husband-and-wife pairs?
Social club committees. A social club contains seven women and four men. The club wants to select a committee of three to represent it at a state convention. How many of the possible committees contain at least one man?
Coin gifts. Among Corey’s collection of early American coins, he has a half-dollar, a quarter, a nickel, and a penny. He wants to give his younger sister some or all of these four coins. How many different sets of coins can Cory give?
Meal possibilities. The university cafeteria offers two choices of soups, three of salad, five of main dishes, and six of desserts. How many different four-course meals can you choose?
In Exercises 67–70, how many distinguishable ways can the letters of each word be arranged?
TAIWAN
AMERICA
SUCCESS
ARRANGE
A company that supplies temporary help has a contract for 20 weeks to provide three workers per week to an insurance firm. The agreement specifies that in no two weeks can the same three workers be sent to work at the firm. How many different workers are necessary?
An FM radio station wants to start its evening programming with five songs every day for 21 days without using the same five songs on any two days. What is the smallest number of songs that can be used to accomplish this result?
In geometry, any two points determine a line. How many lines are determined by 30 given points, no 3 of which lie on the same line?
In geometry, any 3 noncollinear points determine a triangle. How many triangles can be determined by 21 given points, no 3 of which are collinear?
In Exercises 75–82, solve each equation.
(m+1m−1)=3!
6(n−12)=(n+14)
2(n−12)=(n3)
43(k2)=(k+13)
(n0)+(n1)+(n2)+⋯+(nn)=64
(k1)+(k2)+(k3)+⋯+(kk−1)=126
(m4)=(m5)
(n7)=(n3)
How many terms of the form xnym
Use the Fundamental Counting Principle to determine the number of terms in the product
Explain your reasoning.
[Hint: Each term in the product can be obtained by multiplying one term chosen from each factor.]
In Exercises 85–88, the notation n(E) means the number of elements in the set E.
If E={2, 5, 7},
If E={−3,−1},
If E={0},
If E=∅,
In Exercises 89–92 let A={1, 2, 3, 5}
Find n(A) and n(B).
Find A∪B
Find A∩B
Verify that n(A∪B)=n(A)+n(B)−n(A∩B).
In Exercises 93–96, let A={a,b,c}
Find n(A) and n(B).
Find A∪B
Find A∩B
Verify that n(A∪B)=n(A)+n(B)−n(A∩B).