 9.2.1: Suppose team A wins the first three games. How many ways can the se...
 9.2.2: Suppose team A wins the first two games. How many ways can the seri...
 9.2.3: How many ways can a World Series be played if team A wins four game...
 9.2.4: How many ways can a World Series be played if no team wins two game...
 9.2.5: In a competition between players X and Y , the first player to win ...
 9.2.6: One urn contains two black balls (labeled B1 and B2) and one white ...
 9.2.7: One urn contains one blue ball (labeled B1) and three red balls (la...
 9.2.8: A person buying a personal computer system is offered a choice of t...
 9.2.9: Suppose there are three roads from city A to city B and five roads ...
 9.2.10: Suppose there are three routes from North Point to Boulder Creek, t...
 9.2.11: a. A bit string is a finite sequence of 0s and 1s. How many bit str...
 9.2.12: Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4...
 9.2.13: A coin is tossed four times. Each time the result H for heads or T ...
 9.2.14: Suppose that in a certain state, all automobile license plates have...
 9.2.15: A combination lock requires three selections of numbers, each from ...
 9.2.16: a. How many integers are there from 10 through 99? b. How many odd ...
 9.2.17: a. How many integers are there from 1000 through 9999? b. How many ...
 9.2.18: The diagram below shows the keypad for an automatic teller machine....
 9.2.19: Three officersa president, a treasurer, and a secretary are to be c...
 9.2.20: Modify Example 9.2.4 by supposing that a PIN must not begin with an...
 9.2.21: Suppose A is a set with m elements and B is a set with n elements. ...
 9.2.22: a. How many functions are there from a set with three elements to a...
 9.2.23: In Section 2.5 we showed how integers can be represented by strings...
 9.2.24: In each of 2428, determine how many times the innermost loop will b...
 9.2.25: In each of 2428, determine how many times the innermost loop will b...
 9.2.26: In each of 2428, determine how many times the innermost loop will b...
 9.2.27: In each of 2428, determine how many times the innermost loop will b...
 9.2.28: In each of 2428, determine how many times the innermost loop will b...
 9.2.29: Consider the numbers 1 through 99,999 in their ordinary decimal rep...
 9.2.30: Let n = pk1 1 pk2 2 pkm m where p1, p2,..., pm are distinct prime n...
 9.2.31: a. If p is a prime number and a is a positive integer, how many dis...
 9.2.32: a. How many ways can the letters of the word ALGORITHM be arranged ...
 9.2.33: Six people attend the theater together and sit in a row with exactl...
 9.2.34: Five people are to be seated around a circular table. Two seatings ...
 9.2.35: Write all the 2permutations of {W, X, Y, Z}.
 9.2.36: Write all the 3permutations of {s,t, u, v}.
 9.2.37: Evaluate the following quantities. a. P(6, 4) b. P(6, 6) c. P(6, 3)...
 9.2.38: a. How many 3permutations are there of a set of five objects? b. H...
 9.2.39: a. How many ways can three of the letters of the word ALGORITHM be ...
 9.2.40: Prove that for all integers n 2, P(n + 1, 3) = n3 n.
 9.2.41: Prove that for all integers n 2, P(n + 1, 2) P(n, 2) = 2P(n, 1).
 9.2.42: Prove that for all integers n 3, P(n + 1, 3) P(n, 3) = 3P(n, 2).
 9.2.43: Prove that for all integers n 2, P(n, n) = P(n, n 1)
 9.2.44: Prove Theorem 9.2.1 by mathematical induction.
 9.2.45: Prove Theorem 9.2.2 by mathematical induction
 9.2.46: Prove Theorem 9.2.3 by mathematical induction
 9.2.47: A permutation on a set can be regarded as a function from the set t...
Solutions for Chapter 9.2: Possibility Trees and the Multiplication Rule
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 9.2: Possibility Trees and the Multiplication Rule
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4. Since 47 problems in chapter 9.2: Possibility Trees and the Multiplication Rule have been answered, more than 52483 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326. Chapter 9.2: Possibility Trees and the Multiplication Rule includes 47 full stepbystep solutions.

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

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

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.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

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 .

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

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

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.