Count of Commutative Binary Operations with Fixed Identity
Contents |
Theorem
Let $S$ be a set whose cardinality is $n$.
Let $x \in S$.
The number $N$ of possible different commutative binary operations such that $x$ is an identity element that can be applied to $S$ is given by:
- $N = n^{\frac {n \left({n-1}\right)}2}$
Proof
This follows by the arguments of Count of Binary Operations with Fixed Identity and Count of Commutative Binary Operations on a Set.
From Count of Binary Operations on a Set, there are $n^{\left({n^2}\right)}$ binary operations in total.
We also know that $a \in S \implies a \circ x = a = x \circ a$, so all operations on $x$ are already specified.
It remains to count all possible combinations of the remaining $n-1$ elements.
This is effectively counting the mappings $\left({S - \left\{{x}\right\}}\right) \times \left({S - \left\{{x}\right\}}\right) \to S$.
So the question boils down to establishing how many different unordered pairs there are in $\left({S - \left\{{x}\right\}}\right)$.
That is, how many doubleton subsets there are in $\left({S - \left\{{x}\right\}}\right)$.
From Cardinality of Set of Subsets, this is given by:
- $\displaystyle \binom {n - 1} 2 = \frac {\left({n - 1}\right) \left({n - 2}\right)} 2$
To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$. There are clearly $n - 1$ of these.
So the total number of pairs in question is $\displaystyle \frac {\left({n - 1}\right) \left({n - 2}\right)} 2 + n - 1 = \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 & 0 & 1 \\ 2 & 1 & 2 \\ 3 & 3 & 27 \\ 4 & 6 & 4 \ 096 \\ 5 & 10 & 9 \ 765 \ 625 \\ \end{array}$
This sequence is A076113 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).
Sources
- Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $4.2$
