Chapter Summary

Chapter Summary

Key Points

• 1.

  Stirling numbers of the second kind $S(n,k)$ count the number of partitions of $[n]$ into $k$ non-empty blocks, satisfying the recurrence $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$.

• 2.

  Unsigned Stirling numbers of the first kind $c(n,k)$ count permutations of $[n]$ with $k$ cycles, satisfying $c(n,k) = (n-1) \cdot c(n-1,k) + c(n-1,k-1)$.

• 3.

  Bell numbers $B_n = \sum_k S(n,k)$ count all partitions of $[n]$ and have the exponential generating function $e^{e^x - 1}$.

• 4.

  Integer partitions $p(n)$ count representations of $n$ as unordered sums and have Euler's generating function $\prod_k (1-x^k)^{-1}$.

• 5.

  The hypergeometric distribution $\text{Hyp}(N,K,n)$ models sampling without replacement; its variance is smaller than the binomial by the finite population correction $(N-n)/(N-1)$.

• 6.

  As the population $N \to \infty$ with $K/N \to p$, the hypergeometric converges to the binomial $\text{Bin}(n,p)$.

• 7.

  The Poisson limit theorem shows $\text{Bin}(n, \lambda/n) \to \text{Poisson}(\lambda)$: many independent rare events produce a Poisson count.

• 8.

  Le Cam's inequality bounds the Poisson approximation error: $d_{\mathrm{TV}} \leq \sum p_i^2$, which for the homogeneous case is $\lambda p$.

• 9.

  Independent Poisson random variables add: $\text{Poisson}(\lambda_1) + \text{Poisson}(\lambda_2) = \text{Poisson}(\lambda_1 + \lambda_2)$.

• 10.

  The Poisson distribution is the foundational model for packet arrivals, interference events, and user activity in massive access systems.