1. Counting Principles
2. Twelvefold Way
1. Functions from $[m]$ to $[n]$

Remark: We use the notation $[n]$ to denote the first $n$ positive integers. Furthermore, when we mention sets, we are only ever talking about finite sets.

There are three basic counting principles which we will regularly use in these notes. The first is the Sum Rule, which simply states that in $n$ sets with no elements in common, we can find out how many elements are in the union of those sets simply by counting how many elements are in each set. This is obvious enough to me that I will simply state it without proof.

The second counting principle is the Product Rule. It states that in a process with $n$ steps, if there are $a_i$ ways to do the $i^{th}$ step, then there are $\prod_i a_i$ ways to complete the process. An example should help illustrate this. Imagine I want to make a three-letter long string out of the letters A, B, and C, and that the letter C may only appear as the second letter.

The first step is to choose what the first letter should be. There are two options. Then for the second step, I have to pick the second letter. This time, there are three options. Finally, for the third step, I have two options for the third letter.

Notice that the second step shows up twice in this diagram. This is because there were two possible choices before we got to the second step. Thus, by the time the second step is complete, there are 3×2 = 6 possible outcomes.

For each of those 6 outcomes, we still need to pick one of two letters before we are done, leading to a grand total of 6×2 = 12 possible three-letter strings satisfying the criteria we laid out. In principle, this reasoning can be generalized to any step by step procedure with finite choices at each step, which gives us the Product Rule.

The final principle is the hideous Inclusion-Exclusion Principle. It tells us what to do when we want to find out how many elements there are in $n$ sets, but those sets overlap. If there are only two sets $A$ and $B$, this principle is simple enough. You add up the number of elements in $A$ and the number of elements in $B$, and then subtract the number of elements that are in both $A$ and $B$, as otherwise you'd be adding them to the total twice.

$$|A\cup B| = |A| + |B| - |A\cap B|$$

Things get more complicated when we add a third set into the mix. We still have to add up the number of elements in $A$, $B$, and $C$, and then take away the stuff in their intersections to avoid counting them all twice.

But if we do that, then the stuff that is in all three sets is subtracted away three times after being added in three times, so we need to add it in again. The final formula is therefore the unwieldy:

$$|A\cup B| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$$

We state the general formula as follows. Given sets $A_1, \cdots, A_i, \cdots, A_n$:

$$\left|\bigcup_{i \in [n]} A_i\right| = \sum_{I \subseteq [n]} (-1)^{|I| + 1} \left|\bigcap_{i \in I} A_i \right|$$

Proposition 2.1: The number of functions from $[m]$ to $[n]$ is given by $n^m$.

Proof: In order to make a function from $[m]$ to $[n]$, we must choose an element of $[n]$ for each element of $[m]$ to go to. For each element, we have $n$ such choices. We have to make this choice $m$ times, once for each element of $[m]$. Thus, by the Product Rule, there are $n^m$ such functions. $\square$

Proposition 2.2: The number of injective $\varphi: [m] \rightarrow [n]$, where $m \leq n$, is given by $n!/(n-m)!$

Proof: We proceed by induction on the size of the domain. When $m = 1$, we have $n$ choices for where to map the single element of $m$. Thus, the number of injections is $n = n!/(n-1)! = n!/(n-m)!$

Suppose the result holds for some arbitrary $m$. Let us make an injection from $[m+1]$ to $[n]$. First, we need to map the first $m$ elements of $[m+1]$ to their outputs in $[n]$. By the induction hypothesis, there are $n!/(n-m)!$ ways to accomplish this.

Next, we need to pick an element of $[n]$ for $m+1$ to map to. Since this function must be injective, we cannot map to any of the $m$ elements of $[n]$ which are already mapped to. Thus, we only have $n-m$ choices for where $m+1$ should map to. By the Product Rule, this means that the number of possible injections is:

$$\frac{n!}{(n-m)!}(n-m) = \frac{n!}{(n-m-1)!} = \frac{n!}{(n-(m+1))!}$$

Which is the expected result. $\square$