Finding it

Probability Level 5

How many distinct equivalence relations are there on a set of 20 elements?


The answer is 51724158235372.

Ashish Menon by Ashish Menon , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ashish Menon
Feb 21, 2016

The answer is the 20 t h 20th bell number = 1 0 13.71372 10^{13.71372} = 51724158235372

0 Helpful 0 Interesting 0 Brilliant 0 Confused

I do not know all this

Rishabh Sood - 5 years, 3 months ago

Log in to reply

You can think about an equivalence relation as a partition of the set of 20 elements. So you only have to sum up all partitions in k subsets for all possible k.

The number of partitions is S(20,k):

  • If you know Stirling numbers you are done
  • Otherwise think about a partition in k elements as a surjective function from 20 elements to k and calculate how many surjective functions are there using inclusion-exclusion principle and divide that number by k factorial to prevent the order

Brian Riccardi - 5 years, 3 months ago

Log in to reply

Ok, thank you bro!

Rishabh Sood - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...