Discrete Mathematics for Computer Science

Combinatorial Identities 457 Solution. First, restate the problem in terms of urns and balls. How many ways can n balls be put i ...

458 CHAPTER 7 Counting and Combinatorics (Algebraic) n! k! C(n, k) • C(k, m) = k! (n - k)! m! (k - m)! n! k!(n - m)! k!(n - k)! ...

Combinatorial Identities 459 n! k! (n - k)! C(n, k) 0 In the combinatorial proof that the two sets of subsets are disjoint, we ...

460 CHAPTER 7 Counting and Combinatorics (Inductive step) Choose n > no, and assume n E T. Now, prove that n + 1 E T. Begin b ...

Combinatorial Identities 461 Proof. Expand (x + y)f with x = y = 1. 0 Corollary 2: The number of subsets of an n-element set is ...

462 CHAPTER 7 Counting and Combinatorics A second technique for proving identities using binomial coefficients involves recog- n ...

Pascal's Triangle 463 as was proved in Theorem 1 of Section 7.8.1. These coefficients are called multinomial coefficients. Pasca ...

464 CHAPTER 7 Counting and Combinatorics Row 0 1 C(O, 0) Row 1 1 1 C(1, 0) C(1, 1) Row 2 1 2 1 C(2, 0) C(2, 1) C(2, 2) Row 3 1 3 ...

Exercises 465 (b) 12 +^22 +3^2 n (^2) = (2n+l)n(n+l) -+n 6 Proof (a) Since C(k, 1) = k, the sum is found using the column sum fo ...

466 CHAPTER 7 Counting and Combinatorics How many ways can you choose eight letters from aaaaa bbbbbb cccccccc with at least o ...

Exercises 467 A six-person committee is to be chosen from 16 university students, (4 from each class-first, second, third, and ...

468 CHAPTER 7 Counting and Combinatorics Expand (2x - y)^7 using the Binomial Theorem. In the expansion of (3x - 2y)^18 , what ...

Chapter Review 469 for t = 1, 2,..., n - 1. Make a table of the Stirling numbers of the first kind for n = 1,2,3,4,5,6. For a p ...

470 CHAPTER 7 Counting and Combinatorics problems are solved using the Binomial Theorem and techniques for counting permuta- tio ...

Chapter Review 471 THEOREMS Binomial Theorem Pascal's Identity Newton's Identity Sums of Powers 7.12.2 Starting to Review What ...

472 CHAPTER 7 Counting and Combinatorics 4. How many r - digit sequences composed of O's, l's, 2's, and 3's are there in which e ...

Chapter Review 473 available storage locations, but these may be scattered across the disk in pieces too small to use. This sort ...

474 CHAPTER 7 Counting and Combinatorics (c) A self-dual, two-valued boolean function defined on an n-bit binary number whose bi ...

Discrete Probability Expressions of chance and probability are common in everyday language and thinking. We speak of the chance ...

476 CHAPTER 8 Discrete Probability theory is used to design and to analyze the performance of algorithms that are run on compute ...