Introduction

A binary operator over some set S is a function which takes two elements of S and returns another element of S i.e. \(f:S\times{S}\rightarrow{S}\). A classic example is the infinite set \(S=\mathbb{Z}\) with the binary operator of \(+\). Addition obviously takes two numbers and creates another.

The problem is: how many binary operators exist for a finite set S?

I derived this question from “Fundamental Structures of Algebra” by Mostow, on page 9 where they ask some small counting problems about binary operators. I generalised the problems and here we are.

This should be pretty easy for anyone with a bit of time on their hands, so try and solve it yourself then come back and read this.

Arbitrary numbering on S

Any finite set can be arbitrarily numbered. Say I have a set S with \(n:=|S|\). Then there certainly is a bijection between S and \([1,n]\)¹ which imposes some numbering on S. What this means in plain terms is: if you can give me an element of S, I can spit back a unique number for it between 1 and n, and vice versa. This is just for some syntactic sugar so I can write relations and stuff using numbers instead of abstract letters or whatever.

Note I’m not imposing anything else from \([1,n]\) on S, such as its algebraic structure or ordering. You don’t need that to solve this problem. Also \([1,n]=[n]\) just for the ease of writing it.

Easy combinatorics

Take any finite set S and, without loss of generality, apply a numbering to it. Obviously, using the numbering, any binary operator \(S\times{S}\rightarrow{S}\) can be considered a binary operator over \([n]\) i.e. \([n]\times{[n]}\rightarrow{[n]}\).

From the function signature the maths literally falls in our laps. For each of the \(n^2\) possible inputs there are n choices for the output, hence \(\Pi_{i=1}^{n^2}{n}=n^{n^2}\) binary operators we can make.

Another way to come to this solution is that there are \(n^2\) boxes that can fit exactly 1 ball, and you have n choices of ball per box.

Pretty simple overall, and an intuitive solution no less.

Conclusion

I’m hoping to make this a series of posts, possibly leading up to some modicum of the massive theorem classifying finite abelian groups but from the perspective of counting up stuff. I found it quite fun to make this article, and I’ve realised I do a lot of irrelevant mathematics throughout the day. By writing this post up I really formalised my pen-and-paper work though, and I’ve already got some new ideas to try out tomorrow. In particular, how would you count the number of operators that, say, admit an identity element? Or are associative? Or admit inverses (left, right, maybe both)?

All in all, expect a few more posts like this probably. Next post will be on counting commutative binary operators.