Count of Commutative Binary Operations on a Set

Theorem

Let $S$ be a set whose cardinality is $n$.

The number $N$ of possible different commutative binary operations that can be applied to $S$ is given by:

$N = n^{\frac {n \left({n+1}\right)}2}$

Proof

Let $\left({S, \circ}\right)$ be a magma.

From Cardinality of Cartesian Product, there are $n^2$ elements in $S \times S$.

The binary operations $\circ$ is commutative iff:

$\forall x, y \in S: x \circ y = y \circ x$

Thus for every pair of elements $\left({x, y}\right) \in S \times S$, it is required that $\left({y, x}\right) \in S \times S$.

So the question boils down to establishing how many different unordered pairs there are in $S$.

That is, how many doubleton subsets there are in $S$.

From Cardinality of Set of Subsets, this is given by:

$\displaystyle \binom n 2 = \frac {n \left({n - 1}\right)} 2$

To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$. There are clearly $n$ of these.

So the total number of pairs in question is $\displaystyle \frac {n \left({n - 1}\right)} 2 + n = \frac {n \left({n+1}\right)} 2$.

The result follows from Cardinality of Set of All Mappings.

$\blacksquare$

Comment

The number grows rapidly with $n$:

$\begin{array} {c|cr} n & \dfrac {n \left({n+1}\right)}2 & n^{\frac {n \left({n+1}\right)}2}\\ \hline 1 & 1 & 1 \\ 2 & 3 & 8 \\ 3 & 6 & 729 \\ 4 & 10 & 1 \ 048 \ 576 \\ \end{array}$

and so on. This sequence is A023813 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $2.3$