470
CHAPTER 7 Counting and Combinatorics
problems are solved using the Binomial Theorem and techniques for counting permutations 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