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

is it equal to symetric = A*B= B*A

---

Ya commutative means A * B = B * A as mentioned in the answer..

---

@HabibKhan: i have one doubt,,no. of symmetric relations possible in a set of n elements is$2^{(n2+n)/2}$

please correct me if i am wrong..

---

Ya it is fine ..But here the question is about no of binary operations which are commutative..

---

but isn't it right that no. of lower triangular entries =(n^2-n)/2

---

Ya it is true ..But then no problem..

---

@Habibkhan 

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

 But elements in a row or column should not occur repeatedly, right? If yes then when one element is filled in n ways, the other in its row or column can be filled only in (n-1) ways. Please clarify.

---

Every binary operation which is commutative ,with n elements ,will represent  one of all the possible matrices such that all of these matrices have the property that they have similar elements in the lower triangle and upper triangle of the matrix and each individual entry can be filled in n ways. So that is why we restrict to only one half and count number of such matrices possible which concludes to the answer of @habib

Basically we are counting such matrices possible which is equal to number of binary operations possible.

---

can someone explain with example with two or three element , how each slot can can be filled in n ways in Cayley table with commutative relation?

---

Why every entry should have only 'n 'different values it depends on operation that what value filled in that entry.

How we decided that output of any binary operation is between 'n' different values only ?

---

According to definition of Binary operation, "a binary operation is an operation of arity of two whose two domains and one codomain are the same set "(link-https://en.wikipedia.org/wiki/Binary_operation)

Which basically means binary operations are closed. Hence if a∈S and b∈S , (where S is the underlying set ) and |S| =n (number of elements in S is n), then a * b ( * is any binary operation) can be any element of S, hence, a * b has n choices(since |S| =n)

---

for example -$\begin{bmatrix} 1 & 3 &4 \\ 3 & 4 & 5\\ 4 & 5 & 6 \end{bmatrix}$

as we can see this matrix is symmetric means commutative in nature .so we have to fill either lower tringular matrix or upper triangular matrix and other part will copy of that .

so no. of entries in lower triangular matrix =no. of rows natural no. sum {we can see lower triangular matrix rows contains 1,2,3,4......numbers elements}

so no. of entries in lower triangular matrix=$\frac{ n*(n+1)}{2}$

for every element we can fill with n numbers so total no. of binary operations are  $n^\frac{ n*(n+1)}{2}$

---

anyone pls explain what is the meaning here binary operations on n elemnts

I got the methof but unable to link by real problem/

@bikram sir please help

---

This one is really easy to understand https://www.quora.com/How-many-commutative-binary-operations-are-possible-on-a-set-containing-n-elements

---

this solution from stack exchange is good

---

The property of not repeating values in a row or column in Cayley Table is for groups. Here, only closure is required.

---

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

Detailed Video Solution

---

@Deepak Poonia sir the link points back to this question. Please correct it. 

---

Corrected now.

---

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