GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
387 views
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given n) is ___________.
asked in Set Theory & Algebra by Veteran (39.8k points) 263 1328 1946
recategorized by | 387 views

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.

1 Answer

+9 votes
Best answer

Given , the cardinality of set = n

So consequently ,

No of entries in operation table(Cayley table)  =  n2

And hence if we consider lower triangular or upper triangular half , we have : (n2 + 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  =  n(n^2 + n)/2

So 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 commutativ operation table here..

Therefore,

No of possible binary operations which are commutative  = n(n^2 + n)/2

answered by Veteran (89.7k points) 15 58 296
selected by
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..


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23706 Points

  2. Bikram

    17298 Points

  3. Habibkhan

    9336 Points

  4. srestha

    6566 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5188 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4514 Points

  9. manu00x

    4158 Points

  10. sushmita

    4098 Points


Recent Badges

Verified Human Terminator
Verified Human maheshtheng
Nice Answer Ahwan
Renewal Ahwan
Notable Question pranab ray
Notable Question Tuhin Dutta
Great Question jothee
Ancestor santhoshdevulapally
Nice Question Pradip Nichite
Famous Question smartmeet
27,447 questions
35,307 answers
84,718 comments
33,549 users