edited by
6,392 views
43 votes
43 votes
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given $n$) is ___________.
edited by

2 Answers

Best answer
60 votes
60 votes

Given the cardinality of the set $= n.$

Therefore the no: of entries in operation table (Cayley table)  $=n^{2}.$

And hence if we consider lower triangular or upper triangular half , we have : $\dfrac{(n^{2} + n)}{2}.$

And in an operation table , each entry can be filled in $n$ ways by any one element out of given $n$ elements of the set.

So no. of ways we can fill the upper or lower triangular half  $=\large n^{\frac{(n^{2} + n)}{2}}$

Each of these is nothing but an instance of operation table of commutative operation as say $(i,j)$ entry is filled in the table so $(j,i)$ entry will also be the same hence the choice for $(j,i)$ entry is constrained to $1$ as we are concerned about commutative operation table here.

$\therefore$ No of possible binary operations which are commutative  $=\large n^{\frac{(n^{2} + n)}{2}}$

edited by
0 votes
0 votes
cardinality of given set = $n$.

binary operation is like a function defined on base set $S$ like this, $f: S \times S → S$

where, domain = $S \times S$ and co-domain = $S$

total no. of possible pairs in domain = $n^2$

total no. of possible $(a, a)$ pairs in domain = $n$.

these $n$ pairs will have $n$ possiblities in co-domain, each.

so, total no. of ways in which every $(a, a)$ element of domain is connected with exactly one element of co-domain ( satisfying definition of function ) = $n^n$

now, total no. of possible $(a, b)$ pairs where a and b are different = $n^2 - n$.

we can think like this from here:

every pair of $(a, b)$ in $n^2 - n$ pairs will form a small bubble of 2 pairs namely $(a, b)$ and $(b, a)$. we will call them a couple and only 1 pair of the 2 will need to choose for both of them.

total no. of such possible couples = $\frac{n^2 - n}{2}$

now each couple will choose an element out of $n$ elements from co-domain.

so, total no. of ways in which a couple can choose exactly one element from co-domain = $n^{\frac{n^2 - n}{2}}$

now, on combining both the results:

total no. of possible commutative functions (binary operations) = $n^n \times n^{\frac{n^2 - n}{2}} = n^{\frac{n^2 + n}{2}}$

Related questions

21 votes
21 votes
6 answers
1
makhdoom ghaya asked Nov 27, 2016
7,045 views
The transitive closure of the relation $\left\{(1, 2), (2, 3), (3, 4), (5, 4)\right\}$ on the set $\left\{1, 2, 3, 4, 5\right\}$ is ___________.
25 votes
25 votes
4 answers
2
makhdoom ghaya asked Dec 15, 2016
2,762 views
Find the number of single valued functions from set $A$ to another set $B,$ given that the cardinalities of the sets $A$ and $B$ are $m$ and $n$ respectively.
18 votes
18 votes
7 answers
4
makhdoom ghaya asked Nov 27, 2016
3,594 views
Which of the following well-formed formulas are equivalent?$P \rightarrow Q$$\neg Q \rightarrow \neg P$$\neg P \vee Q$$\neg Q \rightarrow P$