Chapter 4 Review
325
7. Input: Value for n
Output: All permutations of the integers 1, … , n
Here is an outline for an alternative to the algorithm
given in Section 4.4 to generate the n! permutations
of the integers {1, … , n}. Use a recursive algorithm.
Once a permutation A of the integers 1, … , k − 1
exists, permutations of the integers 1, … , k can be
obtained by inserting integer k into every possible
position in A. Every time k = n, any permutation so
obtained can be written out. Initiate the process by
sending 1 to an empty permutation list. For the case
n = 3, for example, this algorithm successively
traverses the branches of the tree and prints out the
leaves.
1
2, 1
1, 2
3, 2, 1 2, 3, 1 2, 1, 3 3, 1, 2 1, 3, 2 1, 2, 3
8. Input: Values for a, b, and n
Output: Value of (a + b)
n
a. Use the binomial theorem to compute your
result.
b. Compute a + b and raise this value to the
nth power; compare your answer with that of
part (a).
9. Input: Values for a, b, n, and r, 1 ≤ r ≤ n + 1
Output: rth term in the expansion of (a + b)
n
10. Input: A random variable and a probability distribution for a finite sample space.
Output: The expected value of the random variable.
11. Write a program that allows the user to enter a
value for n, 1 ≤ n ≤ 10, and then queries the user
for the values needed on the right side of Equation
(4) of Section 4.3 (the principle of inclusion and
exclusion) and computes the value of
0 A 1 c c c A n 0
12. Write a program to generate a given number of
rows of Pascal’s triangle. Do this problem in two
ways.
a. Use the definition of Pascal’s triangle (and
perhaps use your answer to compute Exercise
5 as a function).
b. Use recursion and Pascal’s formula.
13. Benford’s law, also called the first-digit law,
states that in many (but not all) large numerical
data sets, the first digit is not equally likely to be
1 through 9. In fact, the probability that the first
digit equals 1, p(1), is about 30%, and the probability for each successive value of the first digit
goes down until p(9) is about 4.6%. The formula
for Benford’s law is
p(d ) = log 10 a1 +
1
d
b
Evidence based on Benford’s law is admissible in
court and has been used to help detect fraudulent
data in accounting, economics, scientific research,
and other areas.
a. Use the given formula to compute the probability of occurrence in the first digit of digits
1−9.
b. Write a program to generate the first 200 Fibonacci numbers and determine whether the first
digits follow Benford’s law.
325
7. Input: Value for n
Output: All permutations of the integers 1, … , n
Here is an outline for an alternative to the algorithm
given in Section 4.4 to generate the n! permutations
of the integers {1, … , n}. Use a recursive algorithm.
Once a permutation A of the integers 1, … , k − 1
exists, permutations of the integers 1, … , k can be
obtained by inserting integer k into every possible
position in A. Every time k = n, any permutation so
obtained can be written out. Initiate the process by
sending 1 to an empty permutation list. For the case
n = 3, for example, this algorithm successively
traverses the branches of the tree and prints out the
leaves.
1
2, 1
1, 2
3, 2, 1 2, 3, 1 2, 1, 3 3, 1, 2 1, 3, 2 1, 2, 3
8. Input: Values for a, b, and n
Output: Value of (a + b)
n
a. Use the binomial theorem to compute your
result.
b. Compute a + b and raise this value to the
nth power; compare your answer with that of
part (a).
9. Input: Values for a, b, n, and r, 1 ≤ r ≤ n + 1
Output: rth term in the expansion of (a + b)
n
10. Input: A random variable and a probability distribution for a finite sample space.
Output: The expected value of the random variable.
11. Write a program that allows the user to enter a
value for n, 1 ≤ n ≤ 10, and then queries the user
for the values needed on the right side of Equation
(4) of Section 4.3 (the principle of inclusion and
exclusion) and computes the value of
0 A 1 c c c A n 0
12. Write a program to generate a given number of
rows of Pascal’s triangle. Do this problem in two
ways.
a. Use the definition of Pascal’s triangle (and
perhaps use your answer to compute Exercise
5 as a function).
b. Use recursion and Pascal’s formula.
13. Benford’s law, also called the first-digit law,
states that in many (but not all) large numerical
data sets, the first digit is not equally likely to be
1 through 9. In fact, the probability that the first
digit equals 1, p(1), is about 30%, and the probability for each successive value of the first digit
goes down until p(9) is about 4.6%. The formula
for Benford’s law is
p(d ) = log 10 a1 +
1
d
b
Evidence based on Benford’s law is admissible in
court and has been used to help detect fraudulent
data in accounting, economics, scientific research,
and other areas.
a. Use the given formula to compute the probability of occurrence in the first digit of digits
1−9.
b. Write a program to generate the first 200 Fibonacci numbers and determine whether the first
digits follow Benford’s law.