GATE CSE 1989 | Question: 1-v

Question

The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given $n$) is ___________.

Comments

@Nitinkumar.097 As the given set contains n elements. Each of those slots (which are supposed to be filled by the elements of the given set) have n choices. For eg: if the given set is {1,2,3} then each cell in the Caley table can be filled with either 1 or 2 or 3 so 3 choices.

---

@krish__ perfect answer, thanks for this beautiful explanation.

---

$\color{red}{\text{Find Video Solution Below:}}$

Detailed Video Solution

Answer 1

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}}$

Comments

@Deepak Poonia Sir ,

Is it true that “The property of not repeating values in a row or column in Cayley Table is for groups. “

So for this reason we will have n choices for each cell of the cayley table??

 

---

The given question is NOT asking for groups.

For a finite group, in the cayley table, No two elements in a row Or in a column can be same.

Do not confuse Group with the commutative binary operation.

Watch the following video solution for this question:

https://youtu.be/tWS2SlFHg7U

You can study Complete Group Theory here(FREE):

https://www.goclasses.in/courses/Discrete-Mathematics-Course-63f9aa9be4b0a8a370cfb0ad 

---

@Deepak Poonia For getting total commutative binary operations, Why we are multiplying n^n and n^(n^2-n)/2 and not adding it?

Answer 2

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}}$