Discrete Mathematics for Computer Science

Permutations and Combinations 437 Using the factorial function, we can express P(n, r) as P(n, r)= n (n - 1)... (n - r + 1) (n • ...

438 CHAPTER 7 Counting and Combinatorics can be arranged in P(4, 4) ways on the second shelf. Therefore, the total number of arr ...

Permutations and Combinations 439 occur together. After the six books are arranged, the location for the three books on op- erat ...

440 CHAPTER 7 Counting and Combinatorics To count the number of possible seating arrangements at a round table, consider the cas ...

Permutations and Combinations 441 Theorem 2. Forn > r >0, C(n, r) - (n,r) P(r, r) (n - r)! r! Proof. The number of r-permu ...

442 CHAPTER 7 Counting and Combinatorics Basic questions about hands for card games include how many hands of a certain kind exi ...

Permutations and Combinations 443 We now look at a noncard problem that uses the same technique for counting. Example 8. An exam ...

444 CHAPTER 7 Counting and Combinatorics The answer to the original question is then found by multiplying this answer by the num ...

Permutations and Combinations 445 Solution. First determine all the different cases that are possible, and then count the num- b ...

446 CHAPTER 7 Counting and Combinatorics IAI n A 3 1, IA 2 N 43 1, and JAI nA 2 n A 3 J. A 1 = {1 23,1 32). A 2 = {1 23,32 1}. A ...

Constructing the kth Permutation 447 As a result of examining the dictionary ordering of the permutations of three and four elem ...

448 CHAPTER 7 Counting and Combinatorics U Exercises A "word" is a string of one or more lowercase letters. How many words can ...

Exercises 449 How many permutations are there for the 26 letters of the alphabet if the five vowels occur together? 12. How ma ...

450 CHAPTER 7 Counting and Combinatorics lottery is based on trying to guess which six randomly picked numbers from the set {1, ...

Counting with Repeated Objects 451 The Old Town Softball League has 16 teams arranged in four groups of four teams each. How ma ...

452 CHAPTER 7 Counting and Combinatorics objects are identical and not distinguishable, as in this case. Sections 7.8-7.10 expla ...

Counting with Repeated Objects 453 We see that the answer is the same in both cases. In general, the order in which letters are ...

454 CHAPTER 7 Counting and Combinatorics The result just given is a generalization of the case in which all n letters of the per ...

Counting with Repeated Objects 455 Solution. By Theorem 1, we get 12! 4! .4! • 4! This count does not take into account, however ...

456 CHAPTER 7 Counting and Combinatorics Proof. Associate with the problem a set of n + k - 1 marks arranged as -- - n ...