Page 460 - Discrete Mathematics and Its Applications

Review Questions 439

16. Find the permutations of {1, 2, 3, 4, 5} that correspond a) 3 b) 89 c) 111
to these integers with respect to the correspondence be- 17. Develop an algorithm for producing all permutations of a
tween Cantor expansions and permutations as described set of n elements based on the correspondence described
in the preamble to Exercise 14. in the preamble to Exercise 14.

Key Terms and Results

TERMS subtraction rule for counting or inclusion–exclusion for
sets: If a task can be done in either n 1 ways or n 2 ways,
combinatorics: the study of arrangements of objects
then the number of ways to do the task is n 1 + n 2 minus
enumeration: the counting of arrangements of objects
the number of ways to do the task that are common to the
tree diagram: a diagram made up of a root, branches leaving two different ways.
the root, and other branches leaving some of the endpoints subtraction rule or inclusion–exclusion for sets:The number
of branches
of elements in the union of two sets is the sum of the number
permutation: an ordered arrangement of the elements of a set of elements in these sets minus the number of elements in
r-permutation: an ordered arrangement of r elements of a set their intersection.
P(n,r): the number of r-permutations of a set with n elements division rule for counting: There are n/d ways to do a task
r-combination: an unordered selection of r elements of a set if it can be done using a procedure that can be carried out
C(n,r): the number of r-combinations of a set with n elements in n ways, and for every way w, exactly d of the n ways
n correspond to way w.

binomial coefficient : also the number of r-combinations
r division rule for sets: Suppose that a finite set A is the union
of a set with n elements of n disjoint subsets each with d elements. Then n =|A|/d.
combinatorial proof: a proof that uses counting arguments the pigeonhole principle: When more than k objects are
rather than algebraic manipulation to prove a result placed in k boxes, there must be a box containing more
Pascal’s triangle: a representation of the binomial coeffi- than one object.
i

cients where the ith row of the triangle contains for the generalized pigeonhole principle: When N objects are
j
j = 0, 1, 2,...,i placed in k boxes, there must be a box containing at least
S(n, j): the Stirling number of the second kind denoting the N/k objects.
number of ways to distribute n distinguishable objects into
j indistinguishable boxes so that no box is empty n!
P(n, r) =
(n − r)!
RESULTS n!
n
C(n, r) = =
product rule for counting: The number of ways to do a proce- r r!(n − r)!
dure that consists of two tasks is the product of the number
n
n+1 n
of ways to do the first task and the number of ways to do Pascal’s identity: = +
k k−1 k
n
the second task after the first task has been done. the binomial theorem: (x + y) = n k = 0 k n x n−k k

y
r
product rule for sets: The number of elements in the Carte- There are n r-permutations of a set with n elements when
sian product of finite sets is the product of the number of repetition is allowed.
elements in each set. There are C(n + r − 1,r) r-combinations of a set with n ele-
sum rule for counting: The number of ways to do a task in ments when repetition is allowed.
one of two ways is the sum of the number of ways to do There are n!/(n 1 ! n 2 !··· n k !) permutations of n objects of k
these tasks if they cannot be done simultaneously. types where there are n i indistinguishable objects of type i
sum rule for sets: The number of elements in the union of for i = 1, 2, 3,...,k.
pairwise disjoint finite sets is the sum of the numbers of the algorithm for generating the permutations of the set
elements in these sets. {1, 2,...,n}
Review Questions

1. Explain how the sum and product rules can be used to 3. a) How can the product rule be used to find the number
find the number of bit strings with a length not exceeding of functions from a set with m elements to a set with
10. n elements?
2. Explain how to find the number of bit strings of length b) How many functions are there from a set with five
not exceeding 10 that have at least one 0 bit. elements to a set with 10 elements?