Sampling with replacement

Let us consider two examples. Benjawan found a nice chocolate shop that sells $10$ kinds of chocolates. In the first example, Benjawan wants to buy a chocolate for each of the four best performing students in this class. How many possibilities does she have? The answer is clearly $10^4$: a chocolate for each student can be picked in $10$ ways. In another scenario, Amelia forgot her PIN code for entering the CS building. The PIN is four digits long. How many possibilities does she need to go through before she tries all possibilities? Again, the answer is $10^4$ (each digit is between $0$ and $9$, so ten possibilities). This type of counting arises in many scenarios in real life, and many of us end up doing it and believing immediately that our calculation is correct.

But is there any formal proof that such a calculation is correct? Let us try to make a general theorem out of it.

Theorem 22

Let $N$ be an $n$-element set and $M$ be an $m$-element set. The number of possible mappings $f: N \rightarrow M$ is $m^n$.

Exercise 57

Prove Theorem 22 by induction on $n \geq 1$.

Notice that our previous counting problems can be reduced to the theorem. Amelia's PIN is just a mapping $f:\{1,2,3,4\} \rightarrow \{0,\ldots, 9\}$ where $f(i)$ is the value of the $i$-th digit. Benjawan's chocolate selection is the same: It is just the number of functions $f: \{s_1,s_2,s_3,s_4\} \rightarrow \{c_1,\ldots, c_{10}\}$ where $s_i$ is the $i$-th ranked student and $c_j$ is the chocolate of type $j$. The mapping $f(s_2) = c_3$ means that the second-ranked student gets the third type of chocolate. Therefore, one may view Theorem 22 as a formal proof in support of counting methods that we have been using all along (e.g., another famous example is that tossing a dice $k$ times results in $6^k$ possibilities).

The next claim is well known to almost everyone, but how many of us actually prove it at least once in our life?

Theorem 23

Any $n$-element set $X$ has exactly $2^n$ subsets.

Proof:

Notice that every subset $A \subseteq X$ can be represented by a function $\chi_A:X \rightarrow \{0,1\}$ where $\chi_A(x) = 1$ if $x \in A$ and $\chi_A(x) = 0$ otherwise. Therefore, counting the number of subsets of $X$ is the same as counting the number of functions $\chi_A$. From the theorem, we have $2^n$ such functions.

One should remark a small gap in the above argument: We take it for granted that the number of functions $\chi_A$ is the same as the number of subsets of $X$. In this case, it is relatively straightforward to see. In particular, showing that two sets $Y$ and $Z$ have exactly the same cardinality can be done by defining a bijection $f: Y \rightarrow Z$.

Definition 1

A function $f: X \rightarrow Y$ is called

• one-to-one if $x \neq y$ implies $f(x) \neq f(y)$,
• onto if for all $y \in Y$, there exists $x$ such that $f(x) = y$, and
• bijection if it is one-to-one and onto.

Bijection often comes in handy as a tool for counting.

Exercise 58

Prove that the function mapping from $A$ to $\chi_A$ is a bijection.

Exercise 59

Prove Theorem 23 by induction on $n$.

Example 21

Let $n\geq 1$. Each $n$-element set $X$ has exactly $2^{n-1}$ subsets of odd size.

Proof:

Let $\mathcal{O}$ and $\mathcal{E}$ be the family¹ of subsets of $X$ of odd and even sizes respectively. Define a bijection $f: \mathcal{O} \rightarrow \mathcal{E}$ as follows. Fix element $a \in X$. Define $f(A) = A - \{a\}$ if $a \in A$ and $f(A) = A \cup \{a\}$ otherwise. Function $f$ is one-to-one since $f(A) = f(B)$ implies that $A=B$ and onto since every set $A \in \mathcal{E}$ is mapped from either $A - \{a\}$ (when $a \in A$) or from $A \cup \{a\}$ (when $a \not\in A$). (do you see how this concludes the proof?).

Exercise 60

Present an alternate proof of the above example by defining a bijection between $\mathcal{O}$ and $\{A: A \subseteq X \setminus \{a\}\}$ (the latter set has $2^{n-1}$ elements from Theorem 23).

Footnotes

1. This is just a fancy name to say that we are referring to a "set of sets". ↩