Sampling without replacement

Let us revisit Benjawan's example. Let us say that she wants to buy different types of chocolates for the four best performing students in this class. Now the number of possibilities should be $10\cdot 9 \cdot 8 \cdot 7$ instead of $10^4$. In the second scenario, if Amelia knows that she would never repeat the digits in her PIN, then she would only need to try $10\cdot 9 \cdot 8 \cdot 7$ possibilities. Such calculations follow from the following general theorem.

Theorem 24 (Sampling without replacement)

There are $m(m-1)\ldots (m-n+1) = \prod_{i=0}^{n-1}(m-i)$ one-to-one mappings $f: N \rightarrow M$ where $|N|=n$ and $|M|=m$ provided that $n \le m$ (otherwise there are no such mappings by pigeonhole's principle).

Proof:

We do induction on $n$. When $n=1$ (the base case), there are $m$ one-to-one mappings from $N$ to $M$. Now, consider any $n$. Recall that $m \geq n$, fix $a \in N$ and choose the value $f(a) \in M$ in one of $m$ possibilities. By the induction hypothesis, there are $(m-1)\ldots ((m-1)-(n-1)+1) = (m-1)\ldots (m-n+1)$ possible mappings from $N \setminus \{a\}$ to $M \setminus \{f(a)\}$. Note that we can use the induction hypothesis since $|M \setminus \{f(a)\}| = m-1 \ge n-1 = |N \setminus \{a\}|$. Altogether, this implies the formula.

Example 22

Let $X$ be an $n$-element set. The number of ordered pairs $(A,B): A \subseteq B \subseteq X$ is $3^n$.

Proof:

The intuition is that there are three possibilities for each $a \in X$: (i) $a \in A, a \in B$, (ii) $a \in B, a \not\in A$, and (iii) $a \not \in A, a \not\in B$. So when we go over all such possibilities, we get $3^n$. To turn this intuition into a formal proof, we want to define a bijection $f$ between $\{(A,B): A \subseteq B \subseteq X\}$ and $\{1,2,3\}^n$ (as the latter has $3^n$ elements). Define $f((A,B)) = (x_1,\ldots, x_n)$ where $x_i$ indicates which one of the three cases above corresponds to the $i$-th element of $X$ (for some fixed arbitrary order of $X$). It is easy to verify that this is one-to-one and onto.