A couple of weeks ago I began a course at work on computational topology. The introduction included the definition of a topological space, which, briefly, is a set and a collection of subsets of that includes the empty set and the set itself, and is closed under (arbitrary) unions and (finite) intersections. To illustrate the idea, the instructor used the simple example of a set with just 3 points. He presented the class with 11 different examples of collections of subsets of , and asked us to identify which collections were topological spaces and which did not satisfy the closure properties above. (See here for a graphical view of similar examples.)

I have a bad habit of always trying to count things. Forget about the topology connection for a moment; since 11 seemed like a strange, rather specific number, it occurred to me to wonder whether this made up *all* possible collections of subsets, or if not, how many more are there? Answering these questions involves some interesting mathematics, including what I suppose is my favorite theorem of all, if I were ever pressed to pick one.

First, we must be precise about what we are counting. Given a set with elements, how many different collections of subsets of are there? It depends on what we mean by “different.” There are distinct collections of subsets, but this counting assumes, for example, that the collection {{}, {*a*}, {*a*,*b*,*c*}} is distinct from the collection {{}, {*b*}, {*a*,*b*,*c*}}, when for our purposes we don’t really care about the distinction between *a* and *b*.

What we want, then, is to group collections of subsets together under a suitable equivalence relation, and count equivalence classes. This gets tricky, because the equivalence classes do not all have the same size. Fortunately, there are some very powerful tools available, including the Orbit-Stabilizer Theorem, Burnside’s Lemma (actually due to Frobenius), and Polya’s Theorem, all of which are applications of the very useful idea of group action on a set.

I won’t bother with the rather tedious calculations here. The punch line is that there are not just 11 but 20 different collections of subsets. However, a separate calculation yields that exactly 9 of these collections correspond to *topological spaces*, so it turns out that the instructor’s original examples included all of these, with just a couple of “failures” thrown in.

Finally, as a result of this exercise, I learned about another interesting application of this same counting problem to switching theory. Computing the first few terms of the sequence of numbers of collections of subsets of elements, and checking the Online Encyclopedia of Integer Sequences, we find sequence A003180, which also counts the number of Boolean functions of variables, unique up to permutation of the inputs. In hindsight, this makes sense; we can represent particular input values to a Boolean function as the subset of inputs that are true (or 1), and characterize a particular Boolean function by the collection of (subsets of) inputs for which the output is true (or 1).