 7.7.1: a) What is a recurrence relation? b) Find a recurrence relation for...
 7.7.2: Explain how the Fibonacci numbers are used to solve Fibonacci's pro...
 7.7.3: a) Find a recurrence relation for the number of steps needed to sol...
 7.7.4: a) Explain how to find a recurrence relation for the number of bit ...
 7.7.5: Define a linear homogeneous recurrence relation of degree k.
 7.7.6: a) Explain how to solve linear homogeneous recurrence relations of ...
 7.7.7: a) Explain how to find f(bk ) where k is a positive integer if f (n...
 7.7.8: a) Derive a divideandconquer recurrence relation for the number o...
 7.7.9: a) Give a formula for the number of elements in the union ofthree s...
 7.7.10: a) Give a formula for the number of elements in the union of four s...
 7.7.11: a) State the principle of inclusionexclusion. b) Outline a proof o...
 7.7.12: Explain how the principle of inclusionexclusion can be used to cou...
 7.7.13: a) How can you count the number of ways to assign m jobs to n emplo...
 7.7.14: Explain how the inclusionexclusion principle can be used to count ...
 7.7.15: a) Define a derangement. b) Why is counting the number of ways a ha...
 7.7.1: A group of 10 people begin a chain letter, with each person sending...
 7.7.2: A nuclear reactor has created 18 grams of a particular radioactive ...
 7.7.3: Every hour the U.S. government prints 10,000 more $1 bills, 4000 mo...
 7.7.4: Suppose that every hour there are two new bacteria in a colony for ...
 7.7.5: Messages are sent over a communications channel using two different...
 7.7.6: A small post office has only 4cent stamps, 6cent stamps, and 10c...
 7.7.7: How many ways are there to form these postages using the rules desc...
 7.7.8: Find the solutions of the simultaneous system of congruences an = a...
 7.7.9: Solve the recurrence relation an = a_dan2 if ao = 1 and al = 2. [H...
 7.7.10: Solvetherecurrencerelation an = a_l a_2 ifao = 2 and al = 2. (See t...
 7.7.11: Find the solution of the recurrence relation an = 3an 1  3an 2 +...
 7.7.12: Find the solution ofthe recurrence relation an = 3an1  3an2 + an...
 7.7.13: Suppose that in Example 4 of Section 7. l a pair of rabbits leaves ...
 7.7.14: Find the solution to the recurrence relation f(n) = 3f(nI5) + 2n\ w...
 7.7.15: Estimate the size of f in Exercise 14 if f is an increasing function.
 7.7.16: Find a recurrence relation that describes the number of comparisons...
 7.7.17: Estimate the number of comparisons used by the algorithm described ...
 7.7.18: Find flan, where a) an = 3. b) an = 4n + 7. c) an = n 2 + n + 1 .
 7.7.19: Let an = 3n3 + n + 2. Find flkan, where k equals a) 2. b) 3. c) 4.
 7.7.20: Suppose that an = P(n), where P is a polynomial of degree d. Prove ...
 7.7.21: Let {an } and Ibn } be sequences of real numbers. Show that fl(anbn...
 7.7.22: Show that if F(x) and G(x) are the generating functions for the seq...
 7.7.23: (Requires calculus) This exercise shows how generating functions ca...
 7.7.24: Suppose that 14 students receive an A on the first exam in a discre...
 7.7.25: There are 323 farms in Monmouth County that have at least one of ho...
 7.7.26: Queries to a database of student records at a college produced the ...
 7.7.27: Students in the school of mathematics at a university major in one ...
 7.7.28: How many terms are needed when the inclusionexclusion principle is ...
 7.7.29: How many solutions in positive integers are there to the equation X...
 7.7.30: How many positive integers less than 1,000,000 are a) divisible by ...
 7.7.31: How many positive integers less than 200 are a) second or higher po...
 7.7.32: How many ways are there to assign six different jobs to three diffe...
 7.7.33: What is the probability that exactly one person is given back the c...
 7.7.34: How many bit strings of length six do not contain four consecutive Is?
 7.7.35: What is the probability that a bit string oflength six contains at ...
 7.7.1: Given a positive integer n, list all the moves required in the Towe...
 7.7.2: Given a positive integer n and an integer k with I :s k :s n, list ...
 7.7.3: Given a positive integer n, list all the bit sequences of length n ...
 7.7.4: Given a positive integer n, write out all ways to parenthesize the ...
 7.7.5: Given a recurrence relation an = Clanl + C2an2, where Cl and C2 a...
 7.7.6: Given a recurrence relationan = Clanl + C2an2 and initial conditi...
 7.7.7: Given arecurrencerelation oftheform/(n) = al(n/b) + c, where a is a...
 7.7.8: Given the number of elements in the intersection of three sets, the...
 7.7.9: Given a positive integer n, produce the formula for the number of e...
 7.7.10: Given positive integers m and n, find the number of onto functions ...
 7.7.11: Given a positive integer n, list all the derangements of the set {I...
 7.7.1: Find the exact value of 1100, 1500, and 11000, where In is the nth ...
 7.7.2: Find the smallest Fibonacci number greater than 1,000,000, greater ...
 7.7.3: Find as many prime Fibonacci numbers as you can. It is unknown whet...
 7.7.4: Write out all the moves required to solve the Tower of Hanoi puzzle...
 7.7.5: Write out all the moves required to use the FrameStewart algorithm...
 7.7.6: Verify the Frame conjecture for solving the Reve's puzzle for n dis...
 7.7.7: Compute the number of operations required to multiply two integers ...
 7.7.8: Compute the number of operations required to multiply two n x n mat...
 7.7.9: Use the sieve of Eratosthenes to find all the primes not exceeding ...
 7.7.10: Find the number of primes not exceeding 10,000 using the method des...
 7.7.11: List all the derangements of {I, 2, 3, 4, 5, 6, 7, 8} .
 7.7.12: Compute the probability that a permutation of n objects is a derang...
 7.7.1: Find the original source where Fibonacci presented his puzzle about...
 7.7.2: Explain how the Fibonacci numbers arise in a variety of application...
 7.7.3: Describe different variations of the Tower of Hanoi puzzle, includi...
 7.7.4: Discuss as many different problems as possible where the Catalan nu...
 7.7.5: Describe the solution of Ulam's problem (see Exercise 28 in Section...
 7.7.6: Discuss variations ofUlam's problem (see Exercise 28 in Section 7.3...
 7.7.7: Define the convex hull ofa set of points in the plane and describe ...
 7.7.8: Look up the definition of the lucky numbers. Explain how they are f...
 7.7.9: Describe how sieve methods are used in number theory. What kind of ...
 7.7.10: Look up the rules of the old French card game ofrencontres. Describ...
 7.7.11: Describe how exponential generating functions can be used to solve ...
 7.7.12: Describe the Polyci theory of counting and the kind of counting pro...
 7.7.13: The probleme des menages (the problem of the households) asks for t...
 7.7.14: Explain how rook polynomials can be used to solve counting problems.
Solutions for Chapter 7: Advanced Counting Techniques
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 7: Advanced Counting Techniques
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Since 87 problems in chapter 7: Advanced Counting Techniques have been answered, more than 39822 students have viewed full stepbystep solutions from this chapter. Chapter 7: Advanced Counting Techniques includes 87 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

Cyclic shift
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. Numerical methods approximate A I b by x j with residual b  Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.

Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b  Ax is orthogonal to all columns of A.

Matrix multiplication AB.
The i, j entry of AB is (row i of A)ยท(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Nullspace matrix N.
The columns of N are the n  r special solutions to As = O.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Singular matrix A.
A square matrix that has no inverse: det(A) = o.

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.