what is the possible number of commutative binary operations that can be defined on a set of n elements?

Question

Please guide the approach , If we have to find commutative operations , then what will the cardinality of the set which would be mapped to a set with $n$ elements ,since for calculating total no of binary operations we have a mapping defined from set of $n^2$ elements to $n$ elements so possible no of binary operations $=n^{n^2}$ ,but how to approach for commutative binary operation ?

Answer 1

Let $A$ be a set with $n$ elements. We want functions $f:A \times A \longrightarrow A$ such that $f(x,y)=f(y,x)$ for all $x,y \in A$.

Let us write $$A \times A = J \cup K=\{(x,x) \, | \, x \in A\} \cup \{(x,y) \, | \, x \neq y, x,y \in A\}.$$ Observe that $|J|=n$ and $|K|=n^2-n$.

To define $f$ on $A \times A$, we need to define $f$ on $J$ and on $K$.

1. For each $(x,x) \in J$ we can assign any of the $n$ values of $A$, this means we have a totality of $n^n$ choices.
2. Without any restrictions, for each $(x,y) \in K$ we can assign any of the $n$ values of $A$ but for commutativity we have to assign the same value for $f(x,y)$ and $f(y,x)$ so in fact we can only assign values to $\frac{n^2-n}{2}$ pairs $(x,y) \in K$. Thus there are a totality of $n^{\frac{(n^2-n)}{2}}$ choices.

So in all the number of commutative binary functions on $A$ is: $$n^n \cdot n^{\frac{(n^2-n)}{2}}=n^{\frac{n(n+1)}{2}}.$$

Second approach:

You can think of each binary function on $A$ as represented by a $n \times n$ matrix such that the $ij-$th entry of the matrix corresponds to $a_i \xrightarrow{f} a_j$.

Without any restrictions, the number of such matrices will be $n^{n^2}$ because each entry can be chosen in $n$ ways and we have a total of $n^2$ entries to fill.

However for commutativity, the diagonal entries $a_{ii}$ can be assigned any of the $n$ values we want but we have to ensure that for $i \neq j$ we should have $a_{ij}=a_{ji}$.

Thus from among the off-diagonal entries we can only choose either the upper-half or the lower half but not both. Thus we have a totality of $n+\frac{n^2-n}{2}$ entries in this matrix that we can choose the value for and each such entry can be filled in $n$ ways.