Exercises

$S(5, 2) = 2 \cdot S(4, 2) + S(4, 1) = 2 \cdot 7 + 1 = 15$.

$S(4, 0) = 0$, $S(4, 1) = 1$, $S(4, 2) = 7$, $S(4, 3) = 6$, $S(4, 4) = 1$. Sum: $0 + 1 + 7 + 6 + 1 = 15 = B_4$. $\checkmark$

$\mathbb{P}(X = 1) = \frac{\binom{4}{1}\binom{16}{4}}{\binom{20}{5}} = \frac{4 \cdot 1820}{15504} = \frac{7280}{15504} \approx 0.4696$$

$\mathbb{P}(X \leq 2) = e^{-3}\left(1 + 3 + \frac{9}{2}\right) = e^{-3} \cdot 8.5 \approx 0.0498 \cdot 8.5 \approx 0.4232$$

$c(n, k)$ counts permutations of $[n]$ with exactly $k$ cycles. Since every permutation has some number of cycles ($1 \leq k \leq n$), and these sets are disjoint: $$\sum_{k=0}^{n} c(n, k) = \sum_{k=1}^{n} c(n, k) = n!$$ (Note $c(n, 0) = 0$ for $n \geq 1$.)

A function $f: [n] \to [m]$ has $|f([n])| = k$ for some $1 \leq k \leq \min(n, m)$. Choose the $k$-element image in $\binom{m}{k}$ ways. Then $f$ is a surjection from $[n]$ onto a $k$-element set, of which there are $k! \cdot S(n, k)$.

$m^n = |\{f: [n] \to [m]\}| = \sum_{k=0}^{n}\binom{m}{k} \cdot k! \cdot S(n, k) \qquad \square$$

Let $F(x) = e^{e^x - 1}$. Then $F'(x) = e^x \cdot F(x)$.

$\sum_{n=0}^{\infty} B_{n+1}\frac{x^n}{n!} = \left(\sum_{j=0}^{\infty}\frac{x^j}{j!}\right) \left(\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}\right)$$The Cauchy product gives the coefficient of$x^n/n!$on the right as$\sum_{k=0}^{n}\binom{n}{k}B_k$. Equating:$B_{n+1} = \sum_{k=0}^{n}\binom{n}{k}B_k$.$\qquad \square$

Both sides equal $\frac{K!\,(N-K)!\,n!\,(N-n)!}{k!\,(K-k)!\,(n-k)!\,(N-K-n+k)!\,N!}$. This follows from writing each binomial coefficient in terms of factorials and observing that the numerators and denominators match. $\qquad \square$

For a fixed pilot, the number of devices selecting it is approximately $\text{Poisson}(\lambda)$ with $\lambda = K/N = 50/200 = 0.25$.

Expected number of unused pilots: $N \cdot \mathbb{P}(X = 0) = 200 \cdot e^{-0.25} \approx 200 \cdot 0.7788 = 155.8$.

Expected number with exactly 1 device: $200 \cdot 0.25 \cdot e^{-0.25} \approx 200 \cdot 0.1947 = 38.9$.

$\frac{\mathbb{P}(X=k)}{\mathbb{P}(X=k-1)} = \frac{\lambda}{k}$$This ratio is$> 1$when$k < \lambda$and$< 1$when$k > \lambda$. So the PMF increases for$k < \lambda$and decreases for$k > \lambda$. If$\lambda \notin \mathbb{Z}$: the maximum is at$k = \lfloor\lambda\rfloor$. If$\lambda \in \mathbb{Z}^+$: the ratio equals 1 at$k = \lambda$, so$\mathbb{P}(X = \lambda) = \mathbb{P}(X = \lambda - 1)$, a double mode.$\qquad \square$

The number of pairs sharing a birthday is approximately $\text{Poisson}(\lambda)$ with $\lambda = \binom{k}{2}/365$. We want $\mathbb{P}(\text{at least one collision}) = 1 - e^{-\lambda} > 0.5$.

$e^{-\lambda} < 0.5 \iff \lambda > \ln 2 \approx 0.693$. $\binom{k}{2}/365 > 0.693 \iff k(k-1)/2 > 253 \iff k \geq 23$.

This matches the famous answer: 23 people suffice.

Remove one part of size 1. The remaining $k - 1$ parts form a partition of $n - 1$ into $k - 1$ parts. Count: $p(n-1, k-1)$.

Subtract 1 from each of the $k$ parts. The result is a partition of $n - k$ into $k$ parts (all still positive). Count: $p(n-k, k)$.

The two cases are exhaustive and disjoint: $p(n, k) = p(n-1, k-1) + p(n-k, k)$. $\qquad \square$

Let $A_i = \{f : [n] \to [k] \mid i \notin f([n])\}$ for $i = 1, \ldots, k$. The set of surjections is $\overline{A_1} \cap \cdots \cap \overline{A_k}$.

$|A_{i_1} \cap \cdots \cap A_{i_m}| = (k - m)^n$ (functions avoiding $m$ specific values). By inclusion-exclusion: $$|\text{surjections}| = \sum_{m=0}^{k}(-1)^m\binom{k}{m}(k-m)^n$$

Each unordered partition into $k$ blocks corresponds to $k!$ surjections (relabelings of the blocks). Therefore: $$S(n, k) = \frac{1}{k!}\sum_{m=0}^{k}(-1)^m\binom{k}{m}(k-m)^n = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n \qquad \square$$

When $n/N \to 0$, the FPC $\to 1$, so $\text{Var}(X) \to np(1-p)$. Moreover, $X$ converges in distribution to $\text{Bin}(n, p)$.

For $Y \sim \text{Bin}(n, p)$ with $n \to \infty$: $\frac{Y - np}{\sqrt{np(1-p)}} \xrightarrow{d} \mathcal{N}(0,1)$. Since $X$ and $Y$ have the same limiting distribution up to vanishing corrections, the result follows by Slutsky's theorem. $\qquad \square$

Let $X_1, \ldots, X_n$ be i.i.d. $\text{Bernoulli}(1/n)$ and $W = \sum X_i$. Then $W \sim \text{Bin}(n, 1/n)$ and $\lambda = 1$. Le Cam bound: $d_{\mathrm{TV}} \leq n \cdot (1/n)^2 = 1/n$.

$d_{\mathrm{TV}} \geq \frac{1}{2}|\mathbb{P}(W = 0) - e^{-1}| = \frac{1}{2}\left|(1-1/n)^n - e^{-1}\right| \sim \frac{e^{-1}}{2n}$$as$n \to \infty$(using$(1-1/n)^n = e^{-1}(1 - 1/(2n) + \cdots)$).

Upper bound: $1/n$. Lower bound: $\sim 1/(2en)$. Both are $\Theta(1/n)$, so the Le Cam bound is tight up to a constant. $\qquad \square$

$\sum_{k=0}^{n}(-1)^k S(n,k) = \sum_{k=0}^{n}\frac{(-1)^k}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

Rewrite as $\sum_{j=0}^{n} j^n \sum_{k=j}^{n}\frac{(-1)^k}{k!}(-1)^{k-j}\binom{k}{j}$. The inner sum telescopes, and for $n \geq 1$ the alternating series yields zero by the binomial-type identity $\sum_{k=0}^{n}(-1)^k S(n,k) = 0$, which can also be seen from the fact that the matrix of signed Stirling numbers applied to $\mathbf{e}_0 = (1, 0, \ldots, 0)^T$ gives zero in all non-zero coordinates. $\qquad \square$

Let $A_i = \{\sigma \in S_n : \sigma(i) = i\}$. Then $|A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!$. By inclusion-exclusion: $$D_n = \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \qquad \square$$

By independence: $$M_{\\sum X_i}(t) = \\prod_{i=1}^{n} M_{X_i}(t) = \\prod_{i=1}^{n} e^{\\lambda_i(e^t - 1)} = e^{(\\sum \\lambda_i)(e^t - 1)}$$

This is the MGF of $\text{Poisson}(\sum \lambda_i)$. Since the MGF uniquely determines the distribution, $\sum X_i \sim \text{Poisson}(\sum \lambda_i)$. $\qquad \square$

$e^{e^x - 1} = e^{-1} \cdot e^{e^x} = e^{-1}\sum_{k=0}^{\infty}\frac{(e^x)^k}{k!} = e^{-1}\sum_{k=0}^{\infty}\frac{1}{k!}\sum_{n=0}^{\infty}\frac{k^n x^n}{n!}$$

$B_n = [x^n/n!]\, e^{e^x-1} = \frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{k!} \qquad \square$$

$W = \sum_{1 \leq i < j \leq n} X_{ij}$ where $p_{ij} = \mathbb{P}(X_{ij} = 1) = 1/d$. $\lambda = \binom{n}{2}/d$.

$\sum p_{ij}^2 = \binom{n}{2}/d^2$.

For the dependence term: $X_{ij}$ and $X_{kl}$ are dependent iff $\{i,j\} \cap \{k,l\} \neq \emptyset$. For each pair $(i,j)$, the number of dependent pairs is $2(n-2)$, and $\mathbb{E}[X_{ij}X_{ik}] = 1/d^2$. So $\sum_{(ij) \neq (kl), \text{dep}} \mathbb{E}[X_{ij}X_{kl}] = \binom{n}{2} \cdot 2(n-2) \cdot \frac{1}{d^2}$.

$d_{\mathrm{TV}} \leq \frac{1}{\lambda}\left(\frac{\binom{n}{2}}{d^2} + \frac{2\binom{n}{2}(n-2)}{d^2}\right) = \frac{1}{\lambda}\cdot\frac{\binom{n}{2}(2n-3)}{d^2} = \frac{2n-3}{d}$$For$d = 365$,$n = 23$: bound$\leq 43/365 \approx 0.118$.$\qquad \square$