Contents
xv
7.2 Counting Principles 423
7.2.1 The Multiplication Principle 424
72.2 Addition Principle 426
7.3 Set Decomposition Principle 428
7.3.1 Counting the Complement 429
73.2 Using the Pigeon-Hole Principle 430
7.3.3 Application: UNIX Logon Passwords 432
7.4 Exercises 433
7.5 Permutations and Combinations 436
7.5.1 Permutations 436
7.5.2 Linear Arrangements 437
75.3 Circular Permutations 439
7.5.4 Combinations 440
7.5.5 Poker Hands 441
75.6 Counting the Complement 443
7.5.7 Decomposition into Subproblems 444
7.6 Constructing the kth Permutation 446
7.7 Exercises 448
7.8 Counting with Repeated Objects 451
7.8.1 Permutations with Repetitions 452
78.2 Combinations with Repetitions 455
7.9 Combinatorial Identities 457
79.1 Binomial Coefficients 459
79.2 Multinomials 462
7.10 Pascal's Triangle 463
7.11 Exercises 465
7.12 Chapter Review 469
712.1 Summary 470
7.12.2 Starting to Review 471
712.3 Review Questions 471
7.12.4 Using Discrete Mathematics in Computer Science 472