A coding system encodes messages using strings of base 4

Problem 1E Find the generating function for the finite sequence 2, 2, 2, 2, 2. 2.

Problem 2E Find the generating function for the linitc sequence 1. 4, 16.64.256. In Exercises 3-8, by a closed form we mean an algebraic expression not involving a summation over a range of values or the use of ellipses.

Find a closed form for the generating function for each of these sequences. (For each sequence, use the most obvious choice of a sequence that follows the pattern of the initial terms listed.) a) \(0,2,2,2,2,2,2,0,0,0,0,0, \ldots\) b) \(0,0,0,1,1,1,1,1,1, \ldots\) c) \(0,1,0,0,1,0,0,1,0,0,1, \ldots\) d) \(2,4,8,16,32,64,128,256, \ldots\) e) \(\left(\begin{array}{l}7 \\ 0\end{array}\right),\left(\begin{array}{l}7 \\ 1\end{array}\right),\left(\begin{array}{l}7 \\ 2\end{array}\right), \ldots,\left(\begin{array}{l}7 \\ 7\end{array}\right), 0,0,0,0,0, \ldots\) f) \(2,-2,2,-2,2,-2,2,-2, \ldots\) g) \(1,1,0,1,1,1,1,1,1,1, \ldots\) h) \(0,0,0,1,2,3,4, \ldots\) Equation Transcription: Text Transcription: 0,2,2,2,2,2,2,0,0,0,0,0, … 0,0,0,1,1,1,1,1,1, … 0,1,0,0,1,0,0,1,0,0,1, … 2,4,8,16,32,64,128,256, … (0^7),(1^7),(2^7),...,(7^7),0,0,0,0,0, 2,-2,2,-2,2,-2,2,-2, … 1,1,0,1,1,1,1,1,1,1, … 0,0,0,1,2,3,4, …

Problem 4E Find a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.)

Problem 5E Find a closed form for the generating function for the sequence {an}, where

Problem 6E Find a closed form for the generating function for the sequence {an}. Where

Problem 7E For each of these genenerating function provide a closed formula for the sequence it determines.

Find the coefficient of \(x^{10}\) in the power series of each of these functions. a) \(\left(1+x^{5}+x^{10}+x^{15}+\cdots\right)^{3}\) b) \(\left(x^{3}+x^{4}+x^{5}+x^{6}+x^{7}+\cdots\right)^{3}\) c) \(\left(x^{4}+x^{5}+x^{6}\right)\left(x^{3}+x^{4}+x^{5}+x^{6}+x^{7}\right)(1+x+\) \(\left.x^{2}+x^{3}+x^{4}+\cdots\right)\) d) \(\left(x^{2}+x^{4}+x^{6}+x^{8}+\cdots\right)\left(x^{3}+x^{6}+x^{9}+\right.\) \(\cdots\left(x^{4}+x^{8}+x^{12}+\cdots\right)\) e) \(\left(1+x^{2}+x^{4}+x^{6}+x^{8}+\cdots\right)\left(1+x^{4}+x^{8}+x^{12}+\right.\) \(\cdots)\left(1+x^{6}+x^{12}+x^{18}+\cdots\right)\) Equation Transcription: Text Transcription: x^10 (1+x^5+x^10+x^15+...)^3 (x^3+x^4+x^5+x^6+x^7+...)^3 (x^4+x^5+x^6)(x^3+x^4+x^5+x^6+x^7)(1+x+x^2+x^3+x^4+...) (x^2+x^4+x^6+x^8+...)x^3+x^6+x^9+)(x^4+x^8+x^12+...) (1+x^2+x^4+x^6+x^8+...)(1+x^4+x^8+x^12+...)(1+x^6+x^12+x^18+...)

Problem 11E Find the coefficient of x10 in the power series of each of these functions.

Problem 13E Use generating functions to determine the number of different ways 10 identical balloons can be given to four children if each child receives at least two balloons.

Problem 10E Find the coefficient of x9 in the power series of each of these functions

Problem 12E Find the coefficient of x12 in the power series of each of these functions.

Problem 17E In how many ways can 25 identical donuts be distributed to four police officers so that each officer gets at least three but no more than seven donuts?

Problem 18E Use generating functions to find the number of ways to select 14 balls from ajar containing 100 red balls, 100 blue balls, and 100 green balls so that no fewer than 3 and no more than 10 blue balls are selected. Assume that the order in which the balls are drawn does not matter.

Problem 19E What is the generating function for the sequence {ck}, where ck is the number of ways to make change for k dollars using $1 bills, $2 bills, $5 bills, and $10 bills?

Problem 16E Use generating function to find the number of ways choose a dozen bagels from three varieties.-egg, salty, and plain –if at least two bagels of each kind but no more than three salty bagels are chosen

Problem 15E Use generating function to determines the number of different ways 15 identical stuffed animals can be given to six children so that each child receives at least one but no more than three stuffed animals.

Problem 14E Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most three action figures.

Problem 20E What is the generating function for the sequence {ck}, where ck represents the number of ways to make change for k pesos using bills worth 10 pesos, 20 pesos, 50 pesos, and 100 pesos?

Problem 22E Give a combinatorial interpretation of the coefficient of x6 in the expansion (1 + x + x2 + x3 +...)3. Use this interpretation to find this number.

Problem 21E Give a combinatorial interpretation of the coefficient of x6 in the expansion (1 + x + x2 + x3 +...)3. Use this interpretation to find this number.

Problem 23E a) What is the generating function for {ak}, where ak is the number of solutions of x1+ x2 +x3 = k when x1 x2, and x3 are integers with x1? 2, 0 ? x1 ? 3, and 2 ? x3 ? 5? ________________ b) Use your answer to part (a) to find a6.

Problem 24E a) What is the generating function for {ak}, where ak is the number of solutions of x1 + x2 +x4+=k when x1,x2,x3,], A3, and A4 are integers with x1 ? 3,1 ? x2?.5.0? 4. and x4 ? 1 ? ________________ b) Use your answer to part (a) to find a7.

Problem 25E Explain how generating functions can be used to find the number of ways in which postage of r cents can be pasted on an envelope using 3-cent. 4-cent. and 20-cent stamps, a) Assume that the order the stamps are pasted on does not matter. ________________ b) Assume that the stamps are pasted in a row and the order in which they are pasted on matters. ________________ c) Use your answer to part (a) to determine the number of ways 46 cents of postage can be pasted on an envelope using 3-cent. 4-cent. and 20-cent stamps when the order the stamps are pasted on does not matter. (Use of a computer algebra program is advised.) ________________ d) Use your answer to part (b) to determine the number of ways 46 cents of postage can be pasted in a row on an envelope using 3-cent, 4-cent, and 20-cent stamps when the order in which the stamps are pasted on matters. (Use of a computer algebra program is advised.)

Problem 27E Use generating functions (and a computer algebra package, if available) to find the number of ways to make change for $1 using a) dimes and quarters. ________________ b) nickels, dimes, and quarters. ________________ c) pennies, dimes, and quarters. ________________ d) pennies, nickels, dimes, and quarters.

Problem 26E a) Show that 1/(1 –x – x2– x3 – x4 – x5 – x6) is the generating function for the number of ways that the sum n can be obtained when a die is rolled repeatedly and the order of the rolls matters. b) Use part (a) to find the number of ways to roll a total of 8 when a die is rolled repeatedly, and the order of the rolls matters. (Use of a computer algebra package is advised.)

Problem 29E Use generating functions to find the number of ways to make change for $100 using a) $10. $20, and $50 bills. ________________ b) $5, $10, $20, and $50 bills. ________________ c) $5, $ 10, $20. and $50 bills if at least one bill of each denomination is used. ________________ d) $5, $10. and S20 bills if at least one and no more than four of each denomination is used.

Problem 28E Use generating functions (and a computer algebra package, if available) to find the number of ways to make change for $I using pennies, nickels, dimes, and quarters with a) no more than 10 pennies. ________________ b) no more than 10 pennies and no more than 10 nickels. ________________ *c) no more than 10 coins.

Problem 31E If G(x) is the generating function for the sequence {ak}, what is the generating function for each of these sequences?

Use generating functions to solve the recurrence relation \(a_{k}=3 a_{k-1}+2\) with the initial condition \(a_{0}=1\). Equation Transcription: Text Transcription: a_k=3_ak-1+2 a_0=1

Use generating functions to solve the recurrence relation \(a_{k}=7 a_{k-1}\) with the initial condition \(a_{0}=5\). Equation Transcription: Text Transcription: a_k=7_ak-1 a_0=5

Problem 34E Use generating functions to solve the recurrence relation with the initial condition a0 = 1.

Problem 35E Use generating functions to solve the recurrence relation ak = 5ak?1 ? 6ak?2 with initial conditions a0 = 6 and a1 = 30.

Problem 37E Use generating functions to solve the recurrence relation ak = 4ak?1 ? 4ak?2 + k2 with initial conditions a0 = 2 and a1 = 5.

Problem 36E Use generating functions to solve the recurrence relation ak = ak?1 + 2ak?2 + 2k with initial conditions a0 = 4 and a1 = 12.

Problem 38E Use generating functions to solve the recurrence relation ak = 2ak?1 + 3ak?2 + 4k + 6 with initial conditions a0 = 20, a1 = 60.

Problem 39E Use generating functions to find an explicit formula for the Fibonacci numbers.

Problem 40E a) Show that if n is a positive integer, then ________________ b) Use the extended binomial theorem and part (a) to show that the coefficient of xn in the expansion of (1 ? 4x) ?1/2 is for all nonnegative integers n.

(Calculus required) Let \(\left\{C_{n}\right\}\) be the sequence of Catalan numbers, that is, the solution to the recurrence relation \(C_{n}=\Sigma_{k=0}^{n-1} C_{k} C_{n-k-1}\) with \(C_{0}=C_{1}=1\) (see Example 5 in Section 8.1). a) Show that if \(G(x)\) is the generating function for the sequence of Catalan numbers, then \(x G(x)^{2}-G(x)+1=0\). Conclude (using the initial conditions) that \(G(x)=(1-\sqrt{1-4 x}) /(2 x)\) b) Use Exercise 40 to conclude that \(G(x)=\sum_{n=0}^{\infty} \frac{1}{n+1}\left(\begin{array}{l} 2 n \\ n \end{array}\right) x^{n}\), so that \(C_{n}=\frac{1}{n+1}\left(\begin{array}{l} 2 n \\ n \end{array}\right)\). c) Show that \(C_{n} \geq 2^{n-1}\) for all positive integers n. Equation Transcription: Text Transcription: {C_n} C_n = the sum of k=0 to n-1 C_k C_n-k-1 C_0 = C_1 = 1 G(x) xG(x)^2 - G(x) + 1 = 0 G(x) = (1-sqrt 1-4x)/(2x) G(x) = the sum of n=0 to infinity 1/n+1 (^2n_n)x^n C_n = 1/n+1 (^2n_n) C_n greater than or equal to 2^n-1

Problem 42E Use generating functions to prove Pascal’s identity: C(n, r) = C(n ? 1. r) + C(n ? 1. r ? 1) when n and r are positive integers with r < n. [Hint: Use the identity (1 + x)n = (1 + x)n?1 + x(1 + x)n ? 1.]

This exercise shows how to use generating functions to derive a formula for the sum of the first \(n\) squares. a) Show that \(\left(x^{2}+x\right) /(1-x)^{4}\) is the generating function for the sequence \(\left\{a_{n}\right\}\), where \(a_{n}=1^{2}+2^{2}+\cdots+n^{2}\). b) Use part (a) to find an explicit formula for the sum \(1^{2}+2^{2}+\cdots+n^{2}\). The exponential generating function for the sequence \(\left\{a_{n}\right\}\) is the series \(\sum_{n=0}^{\infty} \frac{a_{n}}{n !} x^{n}\) For example, the exponential generating function for the sequence 1, 1, 1,... is the function \(\sum_{n=0}^{\infty} x^{n} / n !=e^{x}\). (You will find this particular series useful in these exercises.) Note that \(e^{x}\) is the (ordinary) generating function for the sequence 1, 1, 1/2!, 1/3!, 1/4!,.... Equation Transcription: Text Transcription: n (x^2 + x) / (1-x)^4 {a_n} a_n = 1^2 + 2^2 + cdot + n^2 1^2 + 2^2 + cdot + n^2 {a_n} sum_n=0 ^infty a_n / n! x^n sum_n=0 ^infty x^n / n! = e^x e^x

Use generating functions to prove Vandermonde’s identity: \(C(m+n, r)=\sum_{k=0}^{r} C(m, r-k) C(n, k)\), whenever \(m\), \(n\), and \(r\) are nonnegative integers with \(r\) not exceeding either \(m\) or \(n\). [Hint: Look at the coefficient of \(x^{r}\) in both sides of \((1+x)^{m+n}=(1+x)^{m}(1+x)^{n}\).] Equation Transcription: Text Transcription: C(m+n, r) = sum_k=0 ^r C(m, r-k)C(n, k) m n r x^r (1+x)^m+n = (1+x)^m (1+x)^n

Problem 45E Find a closed form for the exponential generating function for the sequence {an}, where a) an = 2. ________________ b) an = (?1)n. ________________ c) an = 3n. ________________ d) an = n + 1. ________________ e) an = 1/(n+ 1).

Problem 46E Find a closed form for the exponential generating function for the sequence {an}, where a) an = (? 2)n ________________ b) an = ?1. ________________ c) an = n ________________ d) an = n(n ?1) ________________ e) an = 1/((n + l)(n + 2)).

Find the sequence with each of these functions as its exponential generating function. a. \(f(x)=e^{-x}\) b. \(f(x)=3 x^{2 x}\) c. \(f(x)=e^{3 x}-3 e^{2 x}\) d. \(f(x)=(1-x)+e^{-2 x}\) e. \(f(x)=e^{-2 x}-(1 /(1-x))\) f. \(f(x)=e^{-3 x}-(1+x)+(1 /(1-2 x))\) g. \(f(x)=e^{x^{2}}\) Equation Transcription: Text Transcription: f(x) = e^-x f(x) = 3x^2x f(x) = e^3x - 3e^2x f(x) = (1-x) + e^-2x f(x) = e^-2x - (1/(1-x)) f(x) = e^-3x - (1+x)+(1/(1-2x)) f(x) = e^x^2

Problem 48E Find the sequence with each of these functions as its exponential generating function. a) f (x)=e3x ________________ b) f(x)=2e?3x+1 ________________ c) f (x) = e4x + e?4x ________________ d) f (x) = (1 + 2x) + e3x ________________ e) f (x) = ex ? (1/(1 ? x)) ________________ f) f(x) = xex ________________ g) f (x)=

Problem 49E A coding system encodes messages using strings of octal (base 8) digits. A codeword is considered valid if and only if it contains an even number of 7s. a) Find a linear nonhomogeneous recurrence relation for the number of valid codewords of length n. What are the initial conditions? ________________ b) Solve this recurrence relation using Theorem 6 in Section 8.2. ________________ c) Solve this recurrence relation using generating functions.

Problem 50E A coding system encodes messages using strings of base 4 digits (that is, digits from the set {0. 1,2,3}). A codeword is valid if and only if it contains an even number of 0s and an even number of 1s. Let an equal the number of valid codewords of length n. Furthermore, let bn , cn. and dn equal the number of strings of base 4 digits of length n with an even number of 0s and an odd number of 1s, with an odd number of 0s and an even number of 1s, and with an odd number of 0s and an odd number of 1s, respectively. a) Show that dn = 4n ? an ? bn – cn. Use this to show that an + 1 = 2an + bn + cn . bn+ l = bn ? cn + 4n, and cn+1 = cn ? bn + 4n. ________________ b) What are a1, b1, c1 and d1? ________________ c) Use parts (a) and (b) to find a3, b3, c3, and d3. ________________ d) Use the recurrence relations in part (a), together with the initial conditions in part (b), to set up three equations relating the generating functions A(x), B(x), and C(x) for the sequences {an}, {bn}, and {cn}, respectively. ________________ e) Solve the system of equations from part (d) to get explicit formulae for A(x), B(x), and C(x) and use these to get explicit formulae for an, bn, cn, and dn. Generating functions are useful in studying the number of different types of partitions of an integer n. A partition of a positive integer is a way to write this integer as the sum of positive integers where repetition is allowed and the order of the integers in the sum does not matter. For example, the partitions of 5 (with no restrictions) are 1 + 1 + 1 + 1 + 1, 1 + 1 + 1+2, 1 + 1+3, 1+2 + 2, 1 + 4, 2 + 3, and 5. Exercises 51-56 illustrate some of these uses.

Problem 51E Show that the coefficient p(n) of xn in the formal power series expansion of 1/ ((1 ? x)(l –x2)(1 – x3) ···) equals the number of partitions of n.

Problem 52E Show that the coefficient po(n) of xn in the formal power series expansion of 1 / ((1 ? x)(1? x3)(1?x5) ···) equals the number of partitions of n into odd integers, that is, the number of ways to write n as the sum of odd positive integers, where the order does not matter and repetitions are allowed.

Problem 53E Show that the coefficient pd(n) of xn in the formal power series expansion of (1 + x)(1 + x2)(1 + x3) ··· equals the number of partitions of n a into distinct parts, that is, the number of ways to write n as the sum of positive integers, where the order does not matter but no repetitions are allowed.

Problem 54E Find po(n), the number of partitions of n into odd parts with repetitions allowed, and pd(n),the number of partitions of n into distinct parts, for 1 ? n ? 8, by writing each partition of each type for each integer.

Problem 55E Show that if n is a positive integer, then the number of partitions of n into distinct parts equals the number of partitions of n into odd parts with repetitions allowed; that is, po(n) = pd(n). [Hint: Show that the generating functions for po(n) and pd(n) are equal.]

Suppose that \(X\) is a random variable on a sample space \(S\) such that \(X(s)\) is a nonnegative integer for all \(s \in S .\). The probability generating function for \(X\) is \(G_{X}(x)=\sum_{k=0}^{\infty} p(X(s)=k) x^{k}\) (Requires calculus) Show that if \(G_{X}\) is the probability generating function for a random variable \(X\) such that \(X(s)\) is a nonnegative integer for all \(s \in S .\), then a) \(G_{X}(1)=1\). b) \(E(X)=G_{X}^{\prime}(1)\). c) \(V(X)=G_{X}^{\prime \prime}(1)+G_{X}^{\prime}(1)-G_{X}^{\prime}(1)^{2}\). Equation Transcription: Text Transcription: X S X(s) s \in S G_X (x) = sum_k=0 ^infty p(X(s)=k)x^k G_X G_X (1) = 1 E(X) = G_X ^' (1) V(X) = G_X ^'' (1) + G_X ^' (1) - G_X ^' (1)^2

Problem 58E Let X be the random variable whose value is n if the first success occurs on the nth trial when independent Bernoulli trials are performed, each with probability of success p. a) Find a closed formula for the probability generating function Gx. ________________ b) Find the expected value and the variance of X using Exercise 57 and the closed form for the probability generating function found in part (a).

Problem 59E Let m be a positive integer. Let Xm be the random variable whose value is n if the mth success occurs on the (n + m)th trial when independent Bernoulli trials are performed. each with probability of success p. a) Using Exercise 32 in the Supplementary Exercises of Chapter 7. show that the probability generating function GXm is given by GXm (x) = pm/(1 ?qx)m. where q = 1 ? p. ________________ b) Find the expected value and the variance of Xm using Exercise 57 and the closed form for the probability generating function in part (a).

Problem 60E Show that if X and Y are independent random variables on a sample space S such that X(s) and Y(s) are nonnegative integers for all s ? S, then GX+Y(x) = Gx(x)GY(x).