Counting and Sampling Without Replacement

Definition Suppose a procedure is carried out in $k$ stages. Stage 1 has $n_1$ possible results, and for each $j = 2, \dots, k$, stage $j$ has exactly $n_j$ possible results whatever happened at the earlier stages. Then the number of different sequences of results for the whole procedure is

The options available at a stage may depend on the earlier results, as long as their number does not.

Definition For a positive integer $n$, the factorial of $n$ is

and by definition $0! = 1$. Factorials are used here only for nonnegative integers. By the multiplication principle, $n!$ is the number of ways to arrange $n$ distinct objects in a row. The value $0! = 1$ counts the single arrangement of no objects, the empty one. It also keeps the rule $n! = n \cdot (n - 1)!$ true for $n = 1$, and it lets the counting formulas below work when no objects are left over.

Definition For integers $n$ and $k$ with $0 \le k \le n$, a permutation of $k$ objects from $n$ distinct objects is an ordered list of $k$ of the objects with no object repeated. By the multiplication principle the number of such lists is

The product has $k$ factors. For $k = n$ the formula gives $n!/0! = n!$, the arrangements of all the objects, which is where $0! = 1$ is needed. For $k = 0$ it gives $1$, the empty list. Two lists with the same objects in different orders are different permutations.

Definition For integers $n$ and $k$ with $0 \le k \le n$, a combination of $k$ objects from $n$ distinct objects is an unordered selection of $k$ different objects, that is, a subset with $k$ elements. The number of combinations is the binomial coefficient

The formula holds because each subset of size $k$ appears exactly $k!$ times among the $n!/(n - k)!$ permutations, once for each of its orders. In particular $\binom{n}{0} = \binom{n}{n} = 1$, which again relies on $0! = 1$.

Definition Suppose a sample space $\Omega$ is finite and every outcome in it has the same probability $1/\lvert \Omega \rvert$, where $\lvert \Omega \rvert$ is the number of outcomes. Then every event $A \subseteq \Omega$ has probability

Equal likelihood is a property of the selection mechanism and of how the outcomes are described, not of the counting. A simple random sample of size $n$ from $N$ distinct objects gives every one of the $\binom{N}{n}$ subsets the same probability. Drawing one object at a time, each uniformly from those still available, gives every one of the $N!/(N - n)!$ ordered lists the same probability and produces a simple random sample. The favorable count and the total count must describe outcomes at the same level.

Definition In sampling with replacement, each drawn object is returned before the next draw, so every draw is made from the full population and an object can appear more than once. In sampling without replacement, a drawn object is set aside, so a sample of size $n$ from a finite population of $N$ objects contains $n$ different objects and requires $n \le N$. The ratio $n/N$ is the sampling fraction. Uniform draws with replacement are independent. Successive draws without replacement are dependent, because each draw removes an object and changes what the next draw can produce. If the population contains $K$ marked objects and a sample of size $n$ is drawn uniformly without replacement, the chance that it contains exactly $k$ marked objects is

for integers $k$ with $0 \le k \le K$ and $0 \le n - k \le N - K$. This is hypergeometric counting. With replacement, the count of marked objects follows a binomial model with success probability $K/N$ on every draw instead.