Graded: 8.5 #14, 8.6 #10
(It was especially hard to choose problems to be graded, because of the diversity of topics in this assignment. Although no problems from 7.4 or 8.4 are graded, this is not meant to signal that those topics are less important! Linearity of expectation and generating functions will almost certainly appear on the final.)
8.5 #6
a) In this case, $A_1\cup A_2\cup A_3=A_3$, with 10,000 elements.
b) In this case, $|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|=11{,}100$.
c) \begin{align*} |A_1\cup A_2\cup A_3| &= |A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|+|A_1\cap A_2\cap A_3| \\ &= 100 + 1000 + 10000 – 2 – 2 – 2 + 1 \\ &= 11{,}095. \end{align*}
$\bigstar$ 8.5 #14
There are $26!$ permutations, from which we must subtract those containing fish, rat, or bird. A permutation containing fish can be thought of as a permutation of the block ‘fish’ and 22 other letters; there are $23!$ such permutations. Similarly, there are $24!$ permutations containing rat and $23!$ containing bird.
But the answer $26!-23!-24!-23!$ is too small, because some permutations contain fish and rat, and we’ve subtracted those permutations twice. We must add them back in. There are $21!$ permutations of the block ‘fish’, the block ‘rat’, and the other 19 letters.
There are no permutations containing both fish and bird (because of the conflicting i‘s), or both rat and bird (because of the r‘s). So our final answer is $\boxed{26!-23!-24!-23!+21!}$.
8.6 #3
The total number of solutions to $x_1+x_2+x_3=13$ with $x_1,x_2,x_3\in\mathbb N$ is $\binom{13+3-1}{3-1}=105$. From this total, we need to subtract $|A_1\cup A_2\cup A_3|$, where $A_i$ is the number of solutions in which $x_i\ge 6$.
The number of solutions with $x_1\ge 6$ is equal to the number of solutions to $x’_1+x_2+x_3=7$ with $x’_1,x_2,x_3\in\mathbb N$. (Here $x’_1$ has been substituted for $x_1-6$.) This is $\binom{7+3-1}{3-1}=36$. Thus $|A_1|=36$. Similarly, $|A_2|=|A_3|=36$.
The number of solutions with $x_1\ge 6$ and $x_2\ge 6$ is equal to the number of solutions to $x’_1+x’_2+x_3=1$ with $x’_1,x’_2,x_3\in\mathbb N$. This is $\binom{1+3-1}{3-1}=3$. Thus $|A_1\cap A_2|=3$, and the other two-set intersections are the same.
There are no solutions in which $x_1\ge 6$ and $x_2\ge 6$ and $x_3\ge 6$.
By PIE, $|A_1\cup A_2\cup A_3| = 36+36+36-3-3-3+0 = 99$. Thus, 99 of our original 105 solutions are excluded, leaving $\boxed 6$ solutions in which all $x_i$ are less than 6.
Remark. Given that there are only 6 solutions, it would have been easy enough to just list them exhaustively, but I have still provided this solution as an example of PIE.
8.6 #6
First, note that an integer is squarefree if and only if it is not divisible by the square of a prime integer (an exercise for the reader). In particular, a positive integer less than 100 is squarefree if and only if it is not divisible by $2^2$, $3^2$, $5^2$, or $7^2$.
The number of such integers is $$99 – \left(\left\lfloor\frac{99}2^2\right\rfloor+\left\lfloor\frac{99}3^2\right\rfloor+\left\lfloor\frac{99}5^2\right\rfloor+\left\lfloor\frac{99}7^2\right\rfloor\right) + \left\lfloor\frac{99}{(2\cdot 3)^2}\right\rfloor = \boxed{61}.$$ (Note that no further correction terms are needed; if $p,q$ are any pair of distinct primes other than 2 and 3, then no integer less than 100 is divisible by both $p^2$ and $q^2$.)
$\bigstar$ 8.6 #10
We must construct a surjection from the set of 8 balls to the set of 3 bins. According to Theorem 1 in the text (p. 561), this can be done in $3^8-\binom 31\cdot 2^8+\binom 32\cdot 1^8 = \boxed{5796}$ ways.
Remark. An approach based on putting 1 ball in each bin, then putting the remaining 5 balls in any bins, is unlikely to work. Such a process can produce the same outcome in several ways, but not in a consistent number of ways (so we can’t easily correct via division).
It is possible, but labor-intensive, to succeed with a casework approach, where cases are based on the number of balls placed in each bin.
8.6 #18
We use a combinatorial argument.
Let $\sigma=(x_1,x_2,\ldots,x_n)$ be a derangement of $(1,2,\ldots,n)$. Then $x_1=k$ for some $k\in\{2,3,\ldots,n\}$. We consider two cases: $x_k=1$ or $x_k\ne 1$.
Case 1: $x_k=1$, i.e., $\sigma$ exchanges $1$ and $k$. Then $(x_2,x_3,\ldots,x_{k-1},x_{k+1},\ldots,x_n)$ can be any derangement of $(2,3,\ldots,k-1,k+1,\ldots,n)$. For any particular $k$, there are $D_{n-2}$ ways to build that derangement, so there are $D_{n-2}$ ways to build a derangement of $(1,2,\ldots,n)$ that exchanges $1$ and $k$.
Case 2: $x_k\ne 1$. Then $(x_2,x_3,\ldots,x_n)$ can be any derangement of $(2,3,\ldots,k-1,1,k+1,\ldots,n)$. For any particular $k$, there are $D_{n-1}$ ways to build that derangement, so there are $D_{n-1}$ ways to build a derangement of $(1,2,\ldots,n)$ such that $x_1=k$ and $x_k\ne 1$.
Putting the two cases together, we have $D_{n-2}+D_{n-1}$ derangements of $(1,2,\ldots,n)$ for which $x_1=k$. Since there are $n-1$ choices of $k$, the total number of derangements of $(1,2,\ldots,n)$ is $(n-1)(D_{n-2}+D_{n-1})$. That is, $$D_n = (n-1)(D_{n-2}+D_{n-1}).$$
7.4 #7
See back of book.
7.4 #25
Let $p$ be the success probability for each trial (incidentally, the problem was worded badly and should have said “Bernoulli trials with success probability $p$”; I can’t blame anyone who decided to use $p=1/2$).
As suggested in the hint, let $I_j$ be the indicator random variable for the event that a run of successes begins at the $j^{\text{th}}$ trial. Then $R$, the number of runs, is equal to $I_1+I_2+\cdots+I_n$, because each run has one beginning and thus contributes 1 to the total of the $I_j$’s.
By linearity of expectation, we have $E(R)=E(I_1)+E(I_2)+\cdots+E(I_n)$, where $E(I_j)$ is the probability that a run begins at the $j^{\text{th}}$ trial.
For $j=1$, this probability is $p$, because a run begins at the first trial if and only if the first trial is a success. Thus $E(I_1)=p$.
If $2\le j\le n$, then a run begins at the $j^{\text{th}}$ trial if and only if two things occur: the $(j-1)^{\text{th}}$ trial must be a failure and the $j^{\text{th}}$ trial must be a success. The trials are independent, so the probability that these two things happen is $(1-p)\cdot p$. Therefore $E(I_j)=p(1-p)$ for $2\le j\le n$.
Finally, we have $E(R) = p+\underbrace{p(1-p)+p(1-p)+\cdots+p(1-p)}_{n-1\text{ terms}} = \boxed{p+(n-1)(p)(1-p)}$.
7.4 #47
Each ball has probability $\frac{n-1}n$ of not being placed in the first bin. Each ball is placed independently, so the probability that every ball is not placed in the first bin is $\boxed{\left(\frac{n-1}n\right)^m}$.
Remark. If $n$ is large, then this probability is close to $e^{-m/n}$.
7.4 #48
For $1\le j\le m$, let $I_j$ be the indicator random variable for the event that ball $j$ is placed in the first bin. The probability of that event, and thus the expected value of $I_j$, is equal to $1/n$.
The number of balls in the first bin is $I_1+I_2+\cdots+I_m$. Its expected value is $E(I_1)+E(I_2)+\cdots+E(I_m) = \boxed{m/n}$.
7.4 #49
For $1\le j\le n$, let $I_j$ be the indicator random variable for the event that bin $j$ remains empty. By #47 above, $E(I_j)=\left(\frac{n-1}n\right)^m$.
The number of bins that remain empty is $I_1+I_2+\cdots+I_n$. Its expected value is $E(I_1)+E(I_2)+\cdots+E(I_n) = \boxed{n\cdot\left(\frac{n-1}n\right)^m}$, or, equivalently, $\boxed{\frac{(n-1)^m}{n^{m-1}}}$.
8.4 #4
a) $-(1+x+x^2+x^3+x^4+x^5+x^6)$ or $-\frac{1-x^7}{1-x}$
b) $\frac 1{1-3x}$
c) $\frac{3x^2}{1+x}$
d) $\frac 1{1-x}+x$
e) $(1+2x)^7$
f) $-\frac 3{1+x}$
g) $\frac x{1+2x}$
h) $\frac 1{1-x^2}$
8.4 #6
a) $-\frac 1{1-x}$
b) $\frac 1{1-2x}-1$
c) $\frac 1{(1-x)^2}-\frac 2{1-x}$
d) $\frac{e^x-1}x$ (requires some knowledge of Taylor series)
e) $\frac{x^2}{(1-x)^3}$
f) $\frac{(1+x)^{10}-1}x$
8.4 #9, 11 – See back of book
8.4 #18
We want the coefficient of $x^{14}$ in the expansion of $$(1+x+x^2+x^3+\cdots)^2\cdot (x^3+x^4+\cdots+x^{10}).$$ Notice that the $1+x+x^2+x^3+\cdots$ factors don’t need to be truncated at $x^{100}$, since terms of degree higher than 14 are irrelevant to us.
We start by expanding the square factor: $$(1+2x+3x^2+4x^3+\cdots)(x^3+x^4+\cdots+x^{10}).$$ Now the terms of degree 14 are $$(5x^4)(x^10)+(6x^5)(x^9)+(7x^6)(x^8)+\cdots+(12x^{11})(x^3).$$ The total coefficient of $x^{14}$ is $5+6+7+\cdots+12=\boxed{68}$.
8.4 #22
The coefficient of $x^6$ in $(1+x+x^2+x^3+\cdots)^n$ is equal to the number of $n$-tuples of nonnegative integers $(e_1,e_2,\ldots,e_n)$ such that $e_1+e_2+\cdots+e_n=6$. By the methods in $\S$6.5 (“stars and bars”), the number of such $n$-tuples is $\binom{6+n-1}6=\binom{n+5}6=\binom{n+5}{n-1}$, which agrees with the theorem from class concerning the expansion of $\left(\frac 1{1-x}\right)^n$.
8.4 #24
a) \begin{align*} G(x) &= (x^3+x^4+x^5+\cdots)(x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4)(x+x^2+x^3+\cdots) \\ &= x^5(1+x+x^2+\cdots)^2(1+x+x^2+x^3+x^4)^2 \\ &= x^5(1+2x+3x^2+\cdots)(1+2x+3x^2+4x^3+5x^4+4x^5+3x^6+2x^7+x^8). \end{align*} (Note that I expanded in a way conducive to extracting coefficients in part (b); there’s a shorter expression for $G(x)$ as a rational function, but it isn’t particularly helpful here.)
b) The terms in $x^7$ are $x^5(1)(3x^2)+x^5(2x)(2x)+x^5(3x^2)(1)$. Thus $a_7 = (1)(3)+(2)(2)+(3)(1) = 10$.
8.4 #33
Let $A(x)=\sum\limits_{k=0}^\infty a_kx^k$. Then \begin{align*} A(x) &= 1+\sum\limits_{k=1}^\infty a_kx^k \\ &= 1+\sum\limits_{k=1}^\infty (3a_{k-1}+2)x^k \\ &= 1+3\sum\limits_{k=1}^\infty a_{k-1}x^k+2\sum\limits_{k=1}^\infty x^k \\ &= 1+3xA(x)+\frac{2x}{1-x}. \end{align*} We can solve for $A(x)$: \begin{align*} A(x)(1-3x) &= 1+\frac{2x}{1-x} \\ A(x)(1-3x) &= \frac{1+x}{1-x} \\ A(x) &= \frac{1+x}{(1-x)(1-3x)} \end{align*} Expanding, we have \begin{align*} A(x) &= (1+x)(1+x+x^2+\cdots)(1+3x+9x^2+\cdots) \\ &= (1+2x+2x^2+2x^3+\cdots)(1+3x+9x^2+\cdots). \end{align*} The coefficient of $x^k$ is $(1)(3^k)+(2)(3^{k-1}+3^{k-2}+\cdots+3+1)$, which can be simplified to $$a_k = 3^k+2\cdot\frac{3^k-1}{3-1} = \boxed{2\cdot 3^k-1}.$$
8.4 #34
Let $A(x)=\sum\limits_{k=0}^\infty a_kx^k$. Then \begin{align*} A(x) &= 1+\sum_{k=1}^\infty a_kx^k \\ &= 1+\sum_{k=1}^\infty (3a_{k-1}+4^{k-1})x^k \\ &= 1+3\sum_{k=1}^\infty a_{k-1}x^k+\sum_{k=1}^\infty 4^{k-1}x^k \\ &= 1+3xA(x)+\frac x{1-4x}. \end{align*} Solving for $A(x)$ gives \begin{align*} A(x) &= \frac 1{1-3x}\cdot\left(1+\frac x{1-4x}\right) \\ &= \frac 1{1-3x}\cdot\frac{1-3x}{1-4x} \\ &= \frac 1{1-4x} \\ &= 1+4x+4^2x^2+4^3x^3+\cdots. \end{align*} Thus $a_k=4^k$.
8.4 #42
Note that $(1+x)^n = (1+x)(1+x)^{n-1} = (1+x)^{n-1}+x(1+x)^{n-1}$. Thus, the expansions of these polynomials (and all the resulting coefficients) are the same.
The coefficient of $x^r$ in $(1+x)^n$ is $C(n,r)$. The coefficient of $x^r$ in $(1+x)^{n-1}+x(1+x)^{n-1}$ is $C(n-1,r)+C(n-1,r-1)$. Thus $C(n,r)=C(n-1,r)+C(n-1,r-1)$. $\blacksquare$