(a) (b) Figure 1.l
these five positions is the problem of permuting B, C, … , Fin a linear manner, and this can be done in 5! = 120 ways.
To solve the new problem of alternating the sexes, consider the method shown in Fig. l.3(b). A (a female) is placed as before. The next position, clockwise from A, is marked Ml (Male 1) and can be filled in three ways. Continuing clockwise from A, position F2 (Female 2) can be filled in two ways. Proceeding in this manner, by the rule of product, thereare3X 2X 2X 1X 1=12waysinwhichthesesixpeoplecanbearrangedwithno two men or women seated next to each other.
EXERCISES 1.1 AND 1.2
Copyright By PowCoder代写 加微信 powcoder
1. During a local campaign, eight Republican and five Demo- cratic candidates are nominated for president of the school board .
a) If the president is to be one of these candidates, how many possibilities are ther~ for the eventual winner?
b) How many possibilities exist for a pair of candidates (one from each party) to oppose each other for the eventual election? ·
c) Which counting principle is used in part (a)? in part (b)?
2. Answer part (c) of Example 1.6.
3. Buick automobiles come in four models, 12 colors, three engine sizes, and two transmission types. (a) How many distinct Buicks can be manufactured? (b) If one of the available colors is blue, how many different blue Buicks can be manufactured?
4. The board of directors of a pharmaceutical corporation has 10 members. An upcoming stockholders’ meeting is scheduled to approve a new slate of company officers (chosen from the 10 board members).
a) How many different slates consisting of a president, vice president, secretary, and treasurer can the board present to the stockholders for their approval?
~ b) Three members of the board of directors are physicians. How many slates from part (a) have (i) a physician nomi- nated for the presidency? (ii) exactly one physician appear-
ing on the slate? (iii) at least one physician appearing on the slate?
5. While on a Saturday shopping spree Jennifer and Tiffany witnessed two men driving away from the front of a jewelry shop,just before a burglar alarm started to sound. Although ev- erything happened rather quickly, when the two young ladies were questioned they were able to give the police the following information about the license plate (which consisted of two let- ters followed by four digits) on the get-away car. Tiffany was sure that the second letter on the plate was either an O or a Q and the last digit was either a 3 or an 8. Jennifer told the investigator that the first letter on the plate was either a C or a G and that the first digit was definitely a 7. How many different license plates will the police have to check out?
6. To raise money for a new municipal pool, the chamber of commerce in a certain city sponsors a race. Each participant pays a $5 entrance fee and has a chance to win one of the different- sized trophies that are to be awarded to the first eight runners who finish.
a) If 30 people enter the race, in how many ways will it be possible to award the trophies?
b) If Roberta and Candice are two participants in the race, in how many ways can the trophies be awarded with these two runners among the top three?
7. Acertain”BurgerJoint”advertisesthatacustomercanhave his or’her hamburger with or without any or all of the fol- lowing: catsup, mustard, mayonnaise, lettuce, tomato, onion, pickle, cheese, or mushrooms. How many different kinds of hamburger orders are possible?
M30M1 4 2F3 F2
1.2 Permutations 11
12 Chapter 1 Fundamental Principles of Counting
8. Matthew works as a computer operator at a small univer- sity. One evening he finds that 12 computer programs have been submitted earlier that day for batch processing. ln how many ways can Matthew order the processing of these programs if (a) there are no restrictions? (b) he considers four of the pro- grams higher in priority than the other eight and wants to process those four first? (c) he first separates the programs into four of top priority, five of lesser priority, and three of least priority, and he wishes to process the 12 programs in such a way that the top-priority programs are processed first and the three programs of least priority are processed last?
9. Patter’s Pastry Parlor offers eight different kinds of pastry and six different kinds of muffins. In addition to bakery items one can purchase small, medium, or large containers of the fol- lowing beverages: coffee (black, with cream, with sugar, or with cream and sugar), tea (plain, with cream, with -sugar, with cream and sugar, with lemon, or with lemon and sugar), hot cocoa, and orange juice. When Carol comes to Patter’s, in how many ways can she order
a) one bakery item and one medium-sized beverage for herself?
b) one bakery item and one container of coffee for herself and one muffin and one container of tea for her boss, Ms. Didio?
c) one piece of pastry and one container of tea for herself, one muffin and a container of orange juice for Ms. Didio, and one bakery item and one container of coffee for each of her two assistants, Mr. Talbot and Mrs. Gillis?
10. Pamela has 15 different books. In how many ways can she place her books on two shelves so that there is at least one book on each shelf? (Consider the books in each arrangement to be stacked one next to the other, with the first book on each shelf at the left of the shelf.)
11. Three small towns, designated by A, B, and C, are inter- connected by a system of two-way roads, as shown in Fig. 1.4.
b) How many different round trips can Linda travel from townAtotownCandbacktotownA?
c) How many of the round trips in part (b) are such that the return trip (from town C to town A) is at least partially different from the route Linda takes from town A to town C? (For example, if Linda travels from town A to town C along roads R1 and R6, then on her return she might take roads R6and R3, or roads R7 and R2, or road R9, among other possibilities, but she does not travel on roads R6 and R1 .)
List all the permutations for the letters a, c, t.
a) How many permutations are there for the eight letters
a, c, f, g, i, t, w, x?
b) Consider the permutations in part (a). How many start with the letter t? How many start with the letter t and end with the letter c?
Evaluate each of the following.
a) P(7, 2) b) P(8, 4) c) P(IO, 7) d) P(12, 3)
Figure 1.4
a) In how many ways can Linda travel from town A to town C?
16. An alphabet of40 symbols is used for transmitting messages in a communication system. How many distinct messages (lists of symbols) of 25 symbols can the transmitter generate if sym- bols can be repeated in the message? How many if 10 of the 40 symbols can appear only as the first and/or last symbols of the message, the other 30 symbols can appear anywhere, and repetitions of all symbols are allowed?
17. In the Internet each network interface of a computer is as- signed one, or more, Internet addresses. The nature of these Internet addresses is dependent on network size. For the In- ternet Standard regarding reserved network numbers (STD 2), each address is a 32-bit string which falls into one of the fol- lowing three classes: (1) A class A address, used for the largest networks, begins with a 0 which is then followed by a seven-bit network number, and then a 24-bit local address. However, one is restricted from using the network numbers of all O’s or all l’s and the local addresses of all O’s or all 1’s. (2) The class B address is meant for an intermediate-sized network. This ad- dress starts with the two-bit string 10, which is followed by a 14-bit network number and then a 16-bit local address. But the local addresses of all O’s or all l ‘s are not permitted. (3) Class C addresses are used for the smallest networks. These addresses consist of the three-bit string 110, followed by a 21-bit network number, and then an eight-bit local address . Once again the local addresses of all O’s or all 1’s are excluded. How many different addresses of each class are available on the Internet, for this Internet Standard?
18. Morgan is considering the purchase of a low-end computer system. After some careful investigating, she finds that there are seven basic systems (each consisting of a monitor, CPU, key- board, and mouse) that meet her requirements. Furthermore, she
In how many ways can the symbols a, b, c, d,e, e, e, e, e be arranged so that no e is adjacent to another e?
also plans to buy one of four modems, one of three CD ROM drives, and one of six printers. (Here each peripheral device of a given type, such as the modem, is compatible with all seven basic systems.) In how many ways can Morgan configure her low-end computer system?
19. A computer science professor has seven different program- ming books on a bookshelf. Three of the books deal with C++, the other four with Java. In how many ways can the professor arrange these books on the shelf (a) if there are no restrictions? (b) if the languages should alternate? (c) if all the C++ books must be next to each other? (d) if all the C++ books must be next to each other and all the Java books must be next to each other?
20. Over the Internet, data are transmitted in structured blocks of bits called datagrams.
a) In how many ways can the letters in DATAGRAM be arranged?
b) For the arrangements of part (a), how many have all three A’s together?
21. a) How many arrangements are there of all the letters in SOCIOLOGiCAL?
b) In how many p,f the arrangements in part (a) are A and G adjacent?
c) In how many of the arrangements in part (a) are all the vowels adjacent?
22. How many positive integers n can we form using the digits
3, 4, 4, 5, 5, 6, 7 if we want n to exceed 5,000,000?
’23. Twelve clay targets (identical in shape) are arranged in four hanging columns, as shown in Fig. 1.5. There are four red tar- gets in the first column, three white ones in the second column, two green targets in the third column, and three blue ones in the fourth column. To join her college drill team, Deborah must break all 12 of these targets (using her pistol and only 12 bul- lets) and in so doing must always break the existing target at the bottom of a column. Under these conditions, in how many different orders can Deborah shoot down (and break) the 12 targets?
1.2 Permutations 13 24. Showthatforallintegersn,r2’.:0,ifn+1> r,then
P(n+1,r)=( n+ ) P(n,r). n+l-r
25. Find the value(s) of n in each of the following: (a) P(n, 2) =90, (b) P(n, 3) =3P(n, 2), and
(c) 2P(n, 2) + 50 = P(2n, 2).
26. How many different paths in the xy-plane are there from (0, 0) to (7, 7) if a path proceeds one step at a time by go- ing either one space to the right (R) or one space upward (U)? How many such paths are there from (2, 7) to (9, 14)? Can any general statement be made that incorporates these two results?
27. a) How many distinct paths are there from (-1 , 2, 0) to (1, 3, 7) in Euclidean three-space if each move is one of the following types?
Figure 1.S
b) How many such paths are there from (1, 0, 5) to (8, 1, 7)?
c) Generalize the results in parts (a) and (b).
28. a) Determine the value of the integer variable counter af- ter execution of the following program segment. (Here i, j, and k are integer variables.)
counter := O
fori :=1to12do
counter := counter + 1 forj :=5to10do
counter := counter+ 2 fork := 15 downto 8 do
counter := counter+ 3
b) Which counting principle is at play in part (a)?
29. Consider the following program segment where i, j, and k are integer variables.
for i := 1 to 12 do forj :=5to10do
fork :=15 downto 8 do print (i – j)*k
a) How many times is the print statement executed?
b) Which counting principle is used in part (a)?
30. A sequence of letters of the form abcba, where the expres- sion is unchanged upon reversing order, is an example of a palindrome (of five letters). (a) If a letter may appear more than twice, how many palindromes of five letters are there? of six letters? (b) Repeat part (a) under the condition that no letter appears more than twice.
(H): (x, y, z) • (V): (x, y, z) • (A): (x, y, z) •
(x + 1, y, z); (x, y + 1, z); (x, y, z+l)
14 Chapter 1 Fundamental Principles of Counting ABGHFG
Figure 1.6
31. Determine the number of six-digit integers (no leading ze- ros) in which (a) no digit may be repeated; (b) digits may be repeated. Answer parts (a) and (b) with the extra condition that the six-digit integer is (i) even; (ii) divisible by 5; (iii) divisible by 4.
32. a) Provide a combinatorial argument to show that if n and k are positive integers with n = 3k, then n!/(3!l is an in- teger.
b) If two of the people insist on sitting next to each other, how many arrangements are possible?
36. a) In how many ways can eight people, denoted A, B, … , H be seated about the square table shown in Fig. 1.6, where Figs. l .6(a) and l .6(b) are considered the same but are distinct from Fig. l.6(c)?
b) lftwo of the eight people, say A and B, do not get along well, how many different seatings are possible with A and B not sitting next to each other?
37. Sixteen people are to be seated at two circular tables, one of which seats 10 while the other seats six. How many different seating arrangements are possible?
38. A committee of 15-nine women and six men-is to be seated at a circular table (with 15 seats). In how many ways can the seats be assigned so that no two men are seated next to each other?
39. Write a computer program (or develop an algorithm) to determine whether there is a three-digit integer abc(=100a+lOb+c)whereabc=a!+b!+-c!.
b) Generalize the result of part (a).
a) In how many possible ways could a student answer a
JO-question true-false test?
b) In how many ways can the student answer the test in part (a) if it is possible to leave a question unanswered in order to avoid an extra penalty for a wrong answer?
35. a) In how many ways can seven people be arranged about a circular table?
Combinations: The Binomial Theorem
How many distinct four-digit integers can one make from the digits 1, 3, 3, 7, 7, and 8?
The standard deck of playing cards consists of 52 cards comprising four suits: clubs, di- amonds, hearts, and spades. Each suit has 13 cards: ace, 2, 3, … , 9, 10, jack, queen, king. If we are asked to draw three cards from a standard deck, in succession and without replacement, then by the rule of product there are
!= P(52,3)
possibilities, one of which is AH (ace of hearts), 9C (nine of clubs), KD (king of dia- monds) . I f instead we simply select three cards at one time from the deck so that the order of selection of the cards is no longer important, then the six permutations AH-9C-KD, AH-KD-9C, 9C-AH-KD, 9C-KD-AH, KD-9C-AH, and KD-AH-9C all correspond to just one (unordered) selection. Consequently, each selection, or combination, of three cards, with no reference to order, corresponds to 3! permutations of three cards. In equation form
24 Chapter 1 Fundamental Principles of Counting
1. Calculate mand check your answer by listing all the se- lections of size 2 that can be made from the letters a, b, c, d, e, and f.
2. Facingafour-hourbustripbacktocollege,Dianedecidesto take along five magazines from the 12 that her sister has recently acquired. In how many ways can Diane make her selection?
~ 3 ) Evaluate each of the following.
a) C(lO, 4) b) ( \2) c) C(l4, 12)
4. In the Braille system a symbol, such as a lowercase letter, punctuation mark, suffix, and so on, is given by raising at least one of the dots in the six-dot arrangement shown in part (a) of Fig. 1.7. (The six Braille positions are labeled in this part of the figure.) For example, in part (b) of the figure the dots in positions l and 4 are raised and this six-dot arrangement repre- sents the letter c. In parts (c) and (d) of the figure we have the representations for the letters m and t, respectively. The definite article “the” is shown in part (e) of the figure, while part (f) contains the form for the suffix “ow.” Finally, the semicolon, ; , is given by the six-dot arrangement in part (g), where the dots at positions 2 and 3 are raised.
1• •4 2• •5 3• •6
6. If n is a positive integer and n > 1, prove that m+ (” 21) is a perfect square.
(7, A committee of 12 is to be selected from JO men and 10 women. In how many ways can the selection be carried out if (a) there are no restrictions? (b) there must be six men and six women? (c) there must be an even number of women? (d) there must be more women than men? (e) there must be at least eight men?
\ s. In how many ways can a gambler draw five cards from a standard deck and get (a) a flush (five cards of the same suit)? (b) four aces? (c) four of a kind? (d) three aces and two jacks? (e) three aces and a pair? (f) a full house (three of a kind and a
;pair)? (g) three of a kind? (h) two pairs?
9. flow many bytes contain (a) exactly two l’s; (b) exactly
four 1’s; (c) exactly six l’s; (d) at least six l’s?
10. How many ways are there to pick a five-person basketball team from 12 possible players? How many selections include the weakest and the strongest players?
11. Astudentistoanswersevenoutof10questionsonanexam- ination. In how many ways can he make his selection if (a) there are no restrictions? (b) he must answer the first two questions? (c) he must answer at least four of the first six questions?
12. In how many ways can 12 different books be distributed among four children so that (a) each child gets three books? (b) the two oldest children get four books each and the two
f youngest get two books each?
13. How many arrangements of the letters in MISSISSIPPI have no consecutive S’s?
14. A gym coach must select 11 seniors to play on a football team. If he can make his selection in J2,376 ways, how many seniors are eligible to play?
15. a) Fifteen points, no three of which are collinear, are given on a plane. How many lines do they determine?
b) Twenty-five points, no four of which are coplanar, are given in space. How many triangles do they determine? How many planes? How many tetrahedra (pyramidlike solids with four triangular faces)?
16. Determine the value of each of the following summations. 6 2 10
a) I:02+1) h) I:cl-1) c) L[I+(-1/l i=l j=-2 i=O
d) I:c-1l,where n is an odd positive integer k=n
17. Express each of the following using the summation (or Sigma) notation. In parts (a), (d), and (e), ‘n denotes a positive integer.
(b) “c” (c) “m” (d) “t” .•.•..
…. ..•.•.
“the” (f) “ow” (g) Figure 1.7
a) How many different symbols can we represent in the Braille system?
b) How many symbols have exactly three raised dots?
c) Howmanysymbolshaveanevennumberofraiseddots?
5. a) How many permutations of size 3 can one produce with the letters m, r, a, f, and t?
b) List all the combinations of size 3 that result for the letters m, r, a, f, and t.
a)- +-+-+·•·+- n::’.:2 2! 3! 4! n! ‘
a) For parts (a) and (b) of Fig. 1.8 we have two different (though congruent) triangles. These two triangles (distin- guished by their vertices) result from two selections of size 3 from the vertices A, B, C, D, E, F, G, H. How many dif- ferent (whether congruent or not) triangles can we inscribe in the circle in this way?
b) How many different quadrilaterals can we inscribe in the circle, using the marked vertices? [One such quadrilateral appears in part (c) of Fig. 1.8.]
c) Howmanydifferentpolygonsofthreeormoresidescan we inscribe in the given circle by using three or more of the marked vertices?
b) 1 +4 +9 +16 +25 +36 +49 c)13- 23+33- 43+53- 63+73
1.3 Combinations: The Binomial Theorem 25 1. How many triangles are determined by the vertices of a
22. a) In the complete expansion of (a +b +c +d) • (e+f +g+h)(u+v+w+x+y+z)oneobtainsthe sum of terms such as agw, cfx, and dgv. How many such terms appear in this complete expansion?
b) Which of the following terms do not appear in the com- plete expansion from part (a)?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com