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

A binary operation is commutative if changing the order of the operands does not change the result.

Example :

Let  be a set and  be a binary operation on 

Then, * is said to be commutative if, for every x,y,z in , the following identity holds:

x * y = y * x    

Here we change the order of operands x and y  but result is same 

If the above equation holds for particular values of x and y, we say that  x and  y commute.

---

In case of commutative operation $a*b=b*a\,( \forall a,b \in S)$. In case of a binary operation you have $\color{red}{\binom{n}{2} + n}(\text{for diagonal})$ slots to fill in the Cayley's table. The remaining are to be copied. Each slot can take $n$ values. So, $n\times n\times \cdots (\binom{n}{2} + n\text{ times})$ i.e $\,n^{\frac{n^2+n}{2}}$

---

If I take a set A:{1,2,3} and to find out number of binary operation, I'll need to take diagonal elements + either of lower or upper triangular matrix. So in table the places that we have to work out with are $(n^{2} + n)/2$. According to answer each of these place can take n values. Does that mean we have to always consider that the operation is closed under this set??

---

It is nothing but total number of symmetric relations.

---

@krish_ can you please tell why “Each slot can take n values”?

---

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