Discrete Mathematics for Computer Science

470 CHAPTER 7 Counting and Combinatorics

problems are solved using the Binomial Theorem and techniques for counting permuta-

tions with repeated objects. The Binomial Theorem leads to a number of combinatorial

identities that are useful in a variety of counting problems. Pascal's triangle is introduced

and used to prove a number of important combinatorial identities.

Besides solving problems that count the number of ways to arrange objects and design

letter patterns, counting is used as a step in determining the complexity of an algorithm that

solves the TSP. Counting the number of ways to distribute identical objects among other

objects is often seen in probability theory. Even counting the number of integer solutions

for a linear equation with several variables is an application of counting combinations

with repeated objects. The chapter focuses on presenting the foundations for approaching

counting problems rather than focusing on particular problems.

7.12.1 Terms, Theorems, and Algorithms

7.1-7.3 Summary

TERMS

Addition Principle password

complement Pigeon-Hole Principle

crypt subproblems

Multiplication Principle

ALGORITHMS

Traveling Salesperson's Problem (TSP)

7.5-7.6 Summary

TERMS

binomial coefficient fixes

C(n, r) k-th of n! permutations

circular permutation ordering of permutations

combination P (n, r)

derangement permutation

dictionary ordering r-permutation

fixed points

7.8-7.11 Summary

TERMS

algebraic argument multinomial coefficients

columns permutations with repetitions

combinations with repeated elements P (n; ri, r2 .... , rm)

combinations with repetitions Pascal's triangle

combinatorial arguments permutations with repeated letters

combinatorial identities rows

diagonal Stirling numbers of the first kind

multinomial Stirling numbers of the second kind