Our main objective in introducing the notion of functions and the different kinds of functions is to use them to “count”. More specifically, we will use functions to say something about the “size” of a set. But what is the size of a set? This sounds kind of obvious, but in fact, “size” is an informal term and we are rather interested in the notion of the cardinality of a set.
The cardinality of a set $S$ is the number of elements in $S$ and is denoted $|S|$.
If $S$ is finite, then this will be a natural number. So, the size of the set $\{1,2,4,8\}$ would be $|\{1,2,4,8\}| = 4$.
For example, here is another interesting “structure” that we get from thinking about subsets.
The power set of a set $A$ is the set containing all of the subsets of $A$, $$\mathcal P(A) = \{S \mid S \subseteq A\}.$$
Let $A = \{2,3,4\}$. Then the subsets of $A$ are \[\emptyset, \{2\}, \{3\}, \{4\}, \{2,3\}, \{2,4\}, \{3,4\}, \{2,3,4\}.\] There are eight subsets, and $2^3 = 8$.
How big is the power set of a given set? In other words, how many subsets does a given set have?
If $A$ is a finite set, then $|\mathcal P(A)| = 2^{|A|}$.
We will prove this later, in a few ways. However, because of this fact, you’ll sometimes see the power set of a set $A$ denoted by $2^A$.
But why is this quantity important? Consider a problem like the following:
Given a set of $n$ items $\{x_1, \dots, x_n\}$, where each item has a weight $w_i$ and value $v_i$, choose a subset of items that have total weight at most $W$ such that the value of the items chosen is maximized.
This problem is the 0-1 knapsack problem, a combinatorial optimization problem that is not known to be efficiently solvable. Notice that the candidate solutions for this are subsets. This means that a solution that simply searches through all candidate subsets will require exponential time. Figuring out a more clever way of searching through the solution space is what algorithm design is about. And that depends on knowing something about the structure of the problem and its solutions.
The notion of cardinality is fairly straightforward for finite sets and for this reason, we typically think of this as the “size” of the set. However, the question of how to count those elements is not so straightforward. After all, it sounds very easy to do if we have a convenient representation for the set, like a list of all of its members. But we often do not have such a convenient list lying around. So one must develop methods of enumeration. Even then, we may not want to count large quantities by listing each element one at a time. And if $S$ is an infinite set, then things are trickier still.
Now, what role do functions have in this? By the definition of injectivity and surjectivity, a bijection between two sets $A$ and $B$ uniquely pairs each element of $A$ with an element in $B$. One significant consequence of this is that since a bijection pairs each element in the set, both sets must be the same size. This leads us to the following result.
Let $A$ and $B$ be sets. Then
This is fairly straightforward to reason through informally:
Here is one important consequence, called the pigeonhole principle. The name is quite evocative of the result: if you are putting pigeons into holes and have more pigeons than holes, then at least one of the holes is going to contain more than one pigeon.
If $|A| \gt |B|$, then for every function $f : A \to B$, there exist two different elements of $A$ that are mapped by $f$ to the same element of $B$.
Notice that this is just the contrapositive of the fact that if there exists an injective function $f : A \to B$, then $|A| \leq |B|$.
Where did the idea of putting pigeons into holes come from? On the second floor of Crerar, just outside the TA office hour rooms, you'll find the grad student mailboxes. These mail slots are also called pigeonholes. This came from earlier usage, when people really did keep birds in large arrangements of small compartments.
The pigeonhole principle was first stated by Dirichlet in the 1800s and the story goes that it was named as such because Dirichlet's father was a postmaster. However, Dirichlet's naming and statement was in French and German and is rendered as pigeonhole in English. We don't really call these things pigeonholes anymore, and it is probably just as well that we think of birds and holes since it illustrates the basic idea quite nicely: if you have more birds than holes, then one of those holes is going to contain more than one bird.
Notice that the mapping rules work even when the sets in question are not finite.
The cardinality of the natural numbers is defined to be $|\mathbb N| = \aleph_0$. Which sets are the same size as $\mathbb N$? One surprising fact is that $2 \mathbb N = \{n \mid \exists m \in \mathbb N, n = 2\cdot m\}$, the set of even natural numbers has the same cardinality as $\mathbb N$. Why? We can show a bijection $f : \mathbb N \to 2\mathbb N$—define $f(n) = 2n$. This is a bijection because every $n \in \mathbb N$ is paired uniquely with an even number and every even number has an associated $n$.
We say that a set is countable if it is finite or if it has the same cardinality as $\mathbb N$.
Here are some other sets that have cardinality $\aleph_0$:
See if you can figure out a bijection between each of these sets and $\mathbb N$.
The cardinality of the real numbers is $|\mathbb R| = 2^{\aleph_0}$. Based on this, the cardinalities of $\mathbb N$ and $\mathbb R$ are clearly not the same, a fact famously proved by Cantor in 1891. How? In short, he uses a proof by contradiction: for any supposed bijection between $\mathbb N$ and $\mathbb R$, he can show how to construct real numbers that are "missed" by the claimed bijection, contradicting that it’s a bijection.
This brings us to a fun problem for you to think about in your spare time: are there any infinite sets that have cardinality strictly between $|\mathbb N| = \aleph_0$ and $|\mathbb R| = 2^{\aleph_0}$?
It is clear that there is utility in using functions to “count” infinite sets. But here is a fun technical point: this is what we do when we talk about the sizes of finite sets too. When we defined the size of a finite set to be the number of elements in the set, we were really informally defining a bijection. Let $S = \{a_1, \dots, a_n\}$ be a set with $n$ elements. How do we define our bijection? We choose any bijection $f:S \to \{0,1,\dots,n-1\}$. This pairs the two sets together and we can conclude they have the same cardinality: $n$.
This seems a bit strange, because we seem to be counting from 0, but it turns out that this uses a set-theoretic definition of the natural numbers, the von Neumann ordinals.
We define the natural numbers to be
What this looks like is the following:
and so on. We see that each natural number $n \gt 0$ ends up being represented as the set $\{0, \dots, n-1\}$. So in the case of our bijection, we are, in some sense, mapping the size of a finite set directly onto the representation of the natural number that is the number of elements in the set. In a way, this is what counting really is.
While we won’t exactly be coming up with explicit bijections, the basic idea behind them is common in many combinatorial techniques. Namely, if we can describe a set or structure in two different ways (often based on their construction), then we will have shown that the two descriptions are equivalent.
This is a big reason for why combinatorics is essential to a lot of computing problems. In computing, we are often working with discrete structures in some solution space. A brute force algorithm is one that just searches through the solution space. Well, how many solutions could there be? That is a question that can be answered by combinatorial enumeration.
That sounds simple, but notice that in order to enumerate those solutions, we need to know something about the structure of those solutions. And if we know something about the structure of those solutions, that gives us a way to possibly exploit that structure and cleverly discard certain solutions and narrow our search space.
The design of efficient algorithms implicitly does this: we study the problem to try to find ways to cut down our solution space so that we are searching through a much smaller set of possible solutions. Combinatorics gives us the tools to analyze these kinds of structures.
To summarize,
| Property | Standard terminology | Older terminology |
|---|---|---|
| every input has a unique output | injective | one-to-one |
| every element in the range is an output | surjective | onto |
| both of the above | bijective | correspondence |
The standard terminology was popularized in the 1950s due to “Nicolas Bourbaki”, the pseudonym for a collective of French mathematicians founded in the 1930s.
Combinatorics is the study of counting and enumerating objects and their arrangements. In computer science, many of the problems we study are combinatorial optimization problems, in the sense that we want to minimize or maximize some property of some discrete structure or search for a minimal or maximal such object. Combinatorics gives us the tools to analyze and solve these problems.
The structures we are concerned with that we’ll be enumerating are structures that are largely built out of sets. We have already discussed ways to combine sets together to create various constructions. Here, we’ll outline some counting rules based on simple constructions.
First up are cartesian products. Recall that tuples are the constituents of products of sets. In computer science, we often use tuples to tie pieces of information together—these are sometimes also called records or structs. In the theory of algebraic types, these are called product types.
Recall that a colour can be created by mixing different amounts of red, green, and blue light. This can be represented as a 3-tuple $(R, G, B)$.
How many different colours can we represent with such a model? It depends on how we represent the components. In introductory programming, we keep things simple and use an integer from 0 to 255, which happens to be exactly one byte each. Then the number of colours we get is $255 \times 255 \times 255 = 16581375$.
But this is not the only colour model that exists. Another example of a colour model is the HSV model, which breaks colours down into hue, saturation, and value components. This model is represented on a cylinder, where
While this can also be represented using a 3-tuple $(H,S,V)$, each component may use different kinds of values. For instance, it is possible to represent each as a number from 0 to 100. But hue may also be represented in degrees or radians.
Suppose that you’ve been invited to an elaborate dinner party like for a wedding or something. Assuming you have no further dietary restrictions, you are presented with a choice of four starters, three mains, and three desserts. How many different three-course meals can you construct? If we first choose one of the four starters, then for each choice, we have another three choices of mains, and for each of those choices, we have a choice of three desserts. So this gives us $4 \times 3 \times 3 = 36$ different ways to construct our desired meal.
We can think of each course as a set: $S$, $M$, $D$, and so what we’re really doing is asking for the number of tuples that we can get out of these sets, where the first element of the tuple is a starter, the second is a main, and the third is a dessert. In other words, we want to know $|S \times M \times D|$. This gives us a general formula for the size of a Cartesian product.
For finite sets $A_1, A_2, \dots, A_n$, $$|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|.$$
Informally, the product rule describes the number of things you get when you’re given several sets of things to choose from and you can pick one from each.
Let $\Sigma$ be an alphabet of size $k$. How many strings over $\Sigma$ of length $\ell$ are there? Here, we can think of strings in the C programming language sense, as an array of characters, or a tuple. This means that an $\ell$-length string is an $\ell$-tuple belonging to the set $\Sigma \times \Sigma \times \cdots \times \Sigma = \Sigma^\ell$. Applying the product rule, we get that there are $k^\ell$ $\ell$-length strings over $\Sigma$.
Suppose that I have a set $A = \{x_1, x_2, \dots, x_n\}$ with $n$ objects in it. Earlier, we saw the claim that a set of $n$ objects has exactly $2^n$ subsets. Let’s consider the following argument. For each subset $S \subseteq A$, let $w_S$ be a string over the binary alphabet $\{0,1\}$. Then we define $w_S$ by $w_S = a_1 a_2 \cdots w_n$, where for $1 \leq i \leq n$, \[ a_i = \begin{cases} 0 & \text{if $x_i \not \in S$,} \\ 1 &\text{if $x_i \in S$.} \end{cases} \] In other words, we fix some ordering of the elements of $S$ and associate each one to a position in our string. The "bit" associated with item $x_i$ is 1 if $x_i \in S$ and 0 if $x_i \not \in S$.
For instance, $w_\emptyset = 00 \cdots 0 = 0^n$, while $w_A = 11\cdots 1 = 1^n$. How many strings of the form $w_S$ are there? Our prior discussion about the number of strings makes this easy: over the binary alphabet (i.e. two symbols), there are exactly $2^n$ strings of length $n$. The string $w_S$ is sometimes called the characteristic string of $S$.
This is an example of using a bijection to count something. Here, we make use of the fact that we know how to count the number of binary strings quite easily. Then we set up a bijection between the subsets of $S$ and strings of length $n$, where $n = |S|$.
Recall that something else we can do with sets is join them together by using union. In the theory of algebraic types, taking such unions are sometimes called union types but also sum types.
Consider the University of Chicago’s CNetID password policy:
A standard password with a length of 12–18 characters can be used and must contain characters from three of the following categories:
- Uppercase letters
- Lowercase letters
- Numbers (1, 2, 3, etc)
- Symbols, including ! @ # $ % & * ( ) - + = _ | \ [ ] { } < > , . : ; /
Here, we have four distinct categories of symbols,
In other words, we want to make strings over the alphabet $U \cup L \cup N \cup S$. Then how many symbols do we have to make our password? Or, what is $|U \cup L \cup N \cup S|$? Luckily, it’s pretty simple: just add them up. This gives us $26+26+10+26 = 88$ symbols with which we can make passwords. We can state this lemma more generally.
We can state this as a lemma more generally.
For finite disjoint sets $A_1, A_2, \dots, A_n$, $$|A_1 \cup A_2 \cup \cdots \cup A_n| = |A_1| + |A_2| + \cdots + |A_n|.$$
Informally, the sum rule describes a situation where you’re given disjoint sets of things to choose from, but you may only make one choice in total.
For simplicity, let’s consider only passwords of length 12. Taking our discussion above, we know that we can make $$88^{12} = 215,671,155,821,681,003,462,656$$ possible passwords of length 12. This is about $2.1567 \times 10^{23}$, or somewhere around a third of a mole’s worth of particles. However, this doesn’t take into account any of the restrictions on what kinds of symbols must be included.
Consider passwords from the sets $(U \cup L)^{12}$ and $(U \cup N)^{12}$. We seem to be able to apply the product and sum rules here easily, but there’s a catch. The passwords from $U^{12}$ appear in both sets, so if simply added their sizes, we would be double counting this quantity. Thus we get, \begin{align*} |(U \cup L)^{12} \cup (U \cup N)^{12}| &= |(U \cup L)^{12}| + |(U \cup N)^{12}| - |(U \cup L)^{12} \cap (U \cup N)^{12}| \\ &= |(U \cup L)^{12}| + |(U \cup N)^{12}| - |U^{12}| \\ &= 52^{12} + 36^{12} - 26^{12} \\ &= 395,519,958,867,910,127,616 \end{align*}
Here, we made the careful observation that if we take the union of two arbitrary sets, we may have a non-empty intersection. In this case, we need to take care not to count the intersection twice, which the Sum Rule doesn’t account for. This rule is called inclusion-exclusion, or the subtraction rule.
For all finite sets $A$ and $B$, \[|A \cup B| = |A| + |B| - |A \cap B|.\]
The reasoning here is simple: if the intersection of $A$ and $B$ is non-empty, then counting the elements of $A$ and counting the elements of $B$ separately will result in counting the elements in the intersection twice. This means we need to remove one count each of those elements from our total.