GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
98 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 Combinatory by Veteran (28.1k points)   | 98 views

1 Answer

+3 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 (59.7k points)  
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..
Top Users Jan 2017
  1. Debashish Deka

    9614 Points

  2. sudsho

    5554 Points

  3. Habibkhan

    4878 Points

  4. Bikram

    4774 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4408 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4112 Points

  9. Kapil

    3830 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,371 questions
24,203 answers
53,828 comments
20,368 users