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.
But first, what does it mean to count something and what exactly are we counting? To answer those questions, we have to go back and talk about sets a bit more.
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. But we've never talked about the sizes of sets.
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$.
This is fairly straightforward for finite sets. 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 that. And if $S$ is an infinite set, then things are trickier still.
Here is a first 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.
To talk about counting, we need to talk about functions. You may have learned various definitions of what is or isn't a function. Typically, we think of functions in a very calculus kind of way, where we assign a value $x$ to some other value based on some expression like $x^2$. Then, we come across more complicated functions, that are defined piecewise, or maybe weird functions like the Heaviside function or the parity function. Here, we'll make use of the set theory concepts we've just defined to work towards a general definition for functions.
First, recall that a relation is a subset of some cartesian product $X \times Y$, where $X$ is the domain and $Y$ is the co-domain. We can define the following notions on relations.
A relation $R \subseteq A \times B$ is
These properties lead us right to a definition for functions.
A function $f : A \to B$ is a total, single-valued relation with domain $A$ and co-domain $B$. The set $B$ is also called the range of $f$.
We can think of addition as a function $+ : \mathbb Z \times \mathbb Z \to \mathbb Z$. So we can view $+$ as a set that contains pairs, where the first component is a pair of integers $(x,y)$ and the second component is the integer $x+y$. For example, $((2,3), 5) \in +$, but $((-3, 9), 4) \not \in +$.
In other words, a function is really just a relation that satisfy the properties we just defined, totality and single-valued-ness. And so a function is just a set, like everything else in mathematics. The restrictions on the domain and co-domain of the function tracks with our intuitive understanding of functions that we may have learned earlier. For instance, totality guarantees that a function gives us something for every value we throw at it, while single-valuedness guarantees that our function will only give us one possible output for every input that we give it.
(Though technically, totality is not a strict requirement for functions—there are such things as partial functions, which aren't defined for all values of the domain. In this case, we should say that we really care about total functions. This has some consequences in computability theory.)
This is important to keep in mind because this goes back to the idea of description versus computation. From this perspective, there is nothing that says when defining a function we have to say how to compute it. This is but another form of the central question of computer science: we are given function definitions and we define algorithms to compute those functions.
Notice that the terminology of functions in programming confuses things—what programming languages call functions are really particular implementations of algorithms that compute functions. Of course, this makes sense because there's no sense in writing code for a function you can't compute.
We also have different kinds of functions that are important and worth distinguishing.
A function $f:A \to B$ is injective if $$\forall x, y \in A, f(x) = f(y) \rightarrow x = y.$$ Injective functions are also called one-to-one.
The successor function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x+1$ is one-to-one. On the other hand, the function $g:\mathbb N \to \mathbb N$ defined by $g(x) = \left\lfloor \frac x 2 \right\rfloor$ is not one-to-one, since for any even natural number $m$, we have $g(m) = g(m+1)$ but $m \neq m+1$.
The image of a function $f : A \to B$ is the set $\operatorname{im} f = \{f(x) \mid x \in A\}$.
Clearly, $\operatorname{im} f \subseteq \operatorname{rng} f$. However, it is not always the case that $\operatorname{im} f = \operatorname{rng} f$. If it is, we get another special kind of function.
A function $f:A \to B$ is surjective if $\forall y \in B, \exists x \in A, f(x) = y$. Surjective functions are also called onto.
The function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x^2$ is not surjective (for instance, there is no natural number $n$ such that $n^2 = 2$). On the other hand, the function $g(x) = \left\lfloor \frac x 2 \right\rfloor$ from the above example is surjective.
If we combine these two properties, we get an even more special kind of function.
A function $f:A \to B$ is bijective or a bijection if $f$ is both injective and surjective. Bijective functions are also called correspondences.
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. If $B$ were smaller than $A$, then $f$ couldn't be one-to-one, and if $B$ were larger than $A$, then $f$ couldn't be onto.
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}$?
Now, 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$.
As an aside, 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.
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,
| Description | 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.