Prerequisites & Notation

Prerequisites

This chapter builds on the counting foundations from Chapters 2 and 3: binomial coefficients, multinomial coefficients, and the four sampling paradigms (ordered/unordered, with/without replacement). We also use the binomial distribution from Chapter 3.

Binomial coefficients and Pascal's identity(Review ch02)
Self-check: Can you compute $\binom{10}{3}$ and explain why $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ ?
Multinomial coefficients and partitions(Review ch02)
Self-check: Can you compute the number of ways to partition 12 objects into groups of sizes 3, 4, 5?
Four sampling paradigms(Review ch02)
Self-check: Can you state the counting formula for each of the four paradigms (ordered/unordered, with/without replacement)?
Binomial distribution(Review ch03)
Self-check: Can you write down $\mathbb{P}(X = k)$ for $X \sim \text{Bin}(n, p)$ and verify that the PMF sums to 1?
Convergence concepts(Review ch03)
Self-check: Do you understand the notion of a sequence of distributions converging to a limiting distribution?

Chapter Notation

Notation introduced or heavily used in this chapter.

Symbol	Meaning	Introduced
$S(n, k)$	Stirling number of the second kind: number of partitions of $[n]$ into $k$ non-empty subsets
$\left[\begin{smallmatrix} n \\ k \end{smallmatrix}\right]$	Unsigned Stirling number of the first kind: number of permutations of $[n]$ with exactly $k$ cycles
$B_n$	Bell number: total number of partitions of $[n]$
$\text{Hyp}(N, K, n)$	Hypergeometric distribution with population $N$ , success count $K$ , sample size $n$
$\text{Bin}(n, p)$	Binomial distribution with $n$ trials and success probability $p$
$\text{Poisson}(\lambda)$	Poisson distribution with rate parameter $\lambda$
$d_{\mathrm{TV}}(P, Q)$	Total variation distance between distributions $P$ and $Q$
$[n]$	The set $\{1, 2, \ldots, n\}$
$p(n)$	Number of integer partitions of $n$

← Ch 3 Advanced Counting