 7.4.7.4.1: Find the generating function for the finite sequence 2, 2, 2, 2, 2, 2.
 7.4.7.4.2: Find the generating function for the finite sequence 1, 4, 16, 64, ...
 7.4.7.4.3: Find a closed form for the generating function for each ofthese seq...
 7.4.7.4.4: Find a closed form for the generating function for each of these se...
 7.4.7.4.5: Find a closed form for the generating function for the sequence {an...
 7.4.7.4.6: Find a closed form for the generating function for the sequence {an...
 7.4.7.4.7: For each of these generating functions, provide a closed formula fo...
 7.4.7.4.8: For each of these generating functions, provide a closed formula fo...
 7.4.7.4.9: Find the coefficient of x to in the power series of each of these f...
 7.4.7.4.10: Find the coefficient of x9 in the power series of each of these fun...
 7.4.7.4.11: Find the coefficient of x lO in the power series of each of these f...
 7.4.7.4.12: Find the coefficient of x 12 in the power series of each of these f...
 7.4.7.4.13: Use generating functions to determine the number of different ways ...
 7.4.7.4.14: Use generating functions to determine the number of different ways ...
 7.4.7.4.15: Use generating functions to determine the number of different ways ...
 7.4.7.4.16: Use generating functions to find the number of ways to choose a doz...
 7.4.7.4.17: In how many ways can 25 identical donuts be distributed to four pol...
 7.4.7.4.18: Use generating functions to find the number of ways to select 14 ba...
 7.4.7.4.19: What is the generating function for the sequence {cd, where Ck is t...
 7.4.7.4.20: What is the generating function for the sequence {cd, where Ck repr...
 7.4.7.4.21: Give a combinatorial interpretation of the coefficient of X 4 in th...
 7.4.7.4.22: Give a combinatorial interpretation of the coefficient of x6 in the...
 7.4.7.4.23: a) What is the generating function for {ad, where ak is the number ...
 7.4.7.4.24: a) What is the generating function for {ad, where ak is the number ...
 7.4.7.4.25: Explain how generating functions can be used to find the number of ...
 7.4.7.4.26: a) Show that 1/(1  X  x2  x3  X4  x5  X6) is the generating f...
 7.4.7.4.27: Use generating functions (and a computer algebra package, if availa...
 7.4.7.4.28: Use generating functions (and a computer algebra package, if availa...
 7.4.7.4.29: Use generating functions to find the number of ways to make change ...
 7.4.7.4.30: If G(x) is the generating function for the sequence {ak}, what is t...
 7.4.7.4.31: If G(x) is the generating function for the sequence {ad, what is th...
 7.4.7.4.32: Use generating functions to solve the recurrence relation ak = 7ak...
 7.4.7.4.33: Use generating functions to solve the recurrence relation ak = 3ak...
 7.4.7.4.34: Use generating functions to solve the recurrence relation ak = 3ak...
 7.4.7.4.35: Use generating functions to solve the recurrence relation ak = 5ak...
 7.4.7.4.36: Use generating functions to solve the recurrence relation ak = akI...
 7.4.7.4.37: Use generating functions to solve the recurrence relation ak = 4ak...
 7.4.7.4.38: Use generating functions to solve the recurrence relation ak = 2ak_...
 7.4.7.4.39: Use generating functions to find an explicit formula for the Fibona...
 7.4.7.4.40: a) Show that if n is a positive integer, then (1/2) = ( n ) . n (...
 7.4.7.4.41: (Calculus required) Let {Cn} be the sequence of Catalan numbers, th...
 7.4.7.4.42: Use generating functions to prove Pascal's identity: C(n, r) = C(n ...
 7.4.7.4.43: Use generating functions to prove Vandermonde's identity: C(rn + n,...
 7.4.7.4.44: This exercise shows how to use generating functions to derive a for...
 7.4.7.4.45: Find a closed form for the exponential generating function for the ...
 7.4.7.4.46: Find a closed form for the exponential generating function for the ...
 7.4.7.4.47: Find the sequence with each of these functions as its exponential g...
 7.4.7.4.48: Find the sequence with each ofthese functions as its exponential ge...
 7.4.7.4.49: A coding system encodes messages using strings of octal (base 8) di...
 7.4.7.4.50: A coding system encodes messages using strings of base 4 digits (th...
 7.4.7.4.51: Show that the coefficient p(n) of x n in the formal power series ex...
 7.4.7.4.52: Show that the coefficient po(n) of x n in the formal power series e...
 7.4.7.4.53: Show that the coefficient Pd (n) of x n in the formal power seriese...
 7.4.7.4.54: Find po(n), the number of partitions of n into odd parts with repet...
 7.4.7.4.55: Show that if n is a positive integer, then the number of partitions...
 7.4.7.4.56: (Requires calculus) Use the generating function of pen) to show tha...
 7.4.7.4.57: (Requires calculus) Show that if Gx is the probability generating f...
 7.4.7.4.58: Let X be the random variable whose value is n if the first success ...
 7.4.7.4.59: Let m be a positive integer. Let Xm be the random variable whose va...
 7.4.7.4.60: Show that if X and Y are independent random variables on a sample s...
Solutions for Chapter 7.4: Advanced Counting Techniques
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 7.4: 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 60 problems in chapter 7.4: Advanced Counting Techniques have been answered, more than 39773 students have viewed full stepbystep solutions from this chapter. Chapter 7.4: Advanced Counting Techniques includes 60 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (A).

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib IIĀ· Condition numbers measure the sensitivity of the output to change in the input.

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

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

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

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

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

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

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!

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

Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.