Counting and the Four Sampling Methods

Every sampling problem in \S10.3 draws $k$ objects from a set of $n$ distinguishable objects --- picture an urn with balls numbered $1,2,\dots,n$. Two independent yes/no questions fix the setup. (i) Does order matter? In an ordered sample the outcome is a tuple $(s_1,\dots,s_k)$, so $(1,2,5)\neq(2,1,5)$; in an unordered sample the outcome is a set $\{1,2,5\}$ and the draw order is forgotten. (ii) Is the object replaced? With replacement, each drawn object is returned before the next draw, so values may repeat; without replacement, it is set aside, so all $k$ values are distinct and necessarily $k\le n$. Crossing the two questions gives a $2\times2$ grid of four schemes. The section develops the three that yield equally likely outcomes in a natural way and flags the fourth (Remark 10.5). Throughout, the sample space is written $\Omega$ with size $\#\Omega$; when outcomes are equally likely, each one has probability $1/\#\Omega$.

With replacement, order matters (Example 10.6). Each of the $k$ draws independently has all $n$ values available, so by the multiplication principle $\#\Omega=\underbrace{n\cdot n\cdots n}_{k\text{ factors}}=n^k.$ Formally $\Omega=S^k=\{(s_1,\dots,s_k):s_i\in S\}$ with $S=\{1,\dots,n\}$ --- a Cartesian product --- and each tuple has probability $1/n^k$. For an urn of $n=5$ balls with $k=3$ draws, $\#\Omega=5^3=125$. Without replacement, order matters (Example 10.7). Now the first draw has $n$ choices, the second only $n-1$, down to $n-k+1$ for the last, so $\#\Omega=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!},$ where $n!=n(n-1)\cdots2\cdot1$ is the factorial. This needs $k\le n$, and the entries are automatically distinct. For $n=5,\ k=3$: $5\cdot4\cdot3=60=5!/2!$, each tuple of probability $1/60$, and a repeat such as $(2,2,3)$ is simply impossible.

Without replacement, order doesn't matter (Example 10.8). An outcome is now a $k$-element subset of $S$, so $\Omega=\{\omega\subseteq S:\#\omega=k\}$. Its count is the binomial coefficient ('$n$ choose $k$') $\binom{n}{k}=\frac{n!}{(n-k)!\,k!}.$ The key idea: each $k$-subset can be arranged in exactly $k!$ orders, so the $k!$ ordered tuples built from one subset collapse to a single set. Dividing the ordered count by $k!$, $\#\Omega=\frac{n!/(n-k)!}{k!}=\binom{n}{k}.$ For $n=5,\ k=3$: $\binom{5}{3}=10$, each subset of probability $1/10$; a multiset like $\{2,2,3\}$ is not a valid $3$-element set. The fourth scheme (Remark 10.5): with replacement, order doesn't matter. Counting the possible size-$k$ multisets from $n$ types is a named Rule, $\binom{n+k-1}{k}$ (the 'stars and bars' count). But Remark 10.5 warns these multisets are not equally likely --- drawing two balls with replacement from $\{a,b\}$, the mixed result $\{a,b\}$ comes from $ab$ or $ba$ and so is twice as likely as $\{a,a\}$. Since $P=\#A/\#\Omega$ demands equally likely outcomes, we do not use this scheme for probabilities.

On an equally likely space the probability of an event $A$ is the ratio of favorable to total outcomes, $P(A)=\frac{\#A}{\#\Omega}.$ Each probability question thus becomes two counting questions. Remark 10.4 makes a freeing point: an unordered-without-replacement problem may be solved either by counting unordered outcomes or by counting ordered outcomes --- as long as $A$ and $\Omega$ are counted the same way, the ratio is identical. Example 10.9 (Jordan grabs $3$ of $10$ books: $5$ novels, $3$ biographies, $2$ science) finds $P(\text{2 novels},\ \text{1 biography})$ both ways: unordered gives $\binom{10}{3}=120$ total and $\binom{5}{2}\binom{3}{1}=30$ favorable, so $30/120=\tfrac14$; ordered gives $10\cdot9\cdot8=720$ total and $3\cdot3\cdot5\cdot4=180$ favorable, so $180/720=\tfrac14$ --- the same answer. Example 10.10 contrasts the three schemes on one class of $24$ students choosing $3$: with-replacement ordered ($24^3=13{,}824$), without-replacement ordered roles ($24\cdot23\cdot22=12{,}144$), and an unordered team ($\binom{24}{3}=2024$). The correct denominator is dictated entirely by how the selection is actually made.