0
$\begingroup$

How many equivalence relation in $A=\{a,b,c,d,e,f\}$ such that it has exactly 3 classes?

My answer is 90 but my teacher said that 180. Please give me an explanation. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ How did you get 90? What relations / sets of classes did you count? $\endgroup$ – Arthur Dec 3 at 10:00
  • $\begingroup$ I count it in 3 cases. (4,1,1) (3,2,1) and (2,2,2). $\endgroup$ – Soulostar Dec 3 at 10:31
6
$\begingroup$

We count the number of ways of choosing the equivalence classes.

The sizes of the equivalence classes have to be: 4,1,1 or 3,2,1 or 2,2,2.

There are ${6\choose2}$ ways with 4,1,1. [Uniquely determined by picking the two items in size 1 classes]

There are $4{6\choose2}$ ways with 3,2,1 [${6\choose2}$ ways of picking the class size 2, then 4 of picking the class size 1.]

There are 15 ways with 2,2,2: 5 ways of picking the partner of $a$, then 3 ways of dividing the remaining 4.

Hence total 90.

$\endgroup$
3
$\begingroup$

You are correct. There are $\{^6_3\}=90$ equivalence relations on a six-element set that has 3 equivalence classes.

For reference, those are Stirling numbers of the second kind. Similar to how binomial coefficients count subsets of a given size, $\{^n_k\}$ represents the number of partitions with a given number of non-empty parts. And similar to Pascal's identity, you can show the following recurrence relation:

$$\left\{{{n+1}\atop k}\right\}=k\left\{{n\atop k}\right\}+\left\{{n\atop {k-1}}\right\}$$

with $\left\{{0\atop 0}\right\}=1$ and $\left\{{n\atop 0}\right\}=\left\{{0\atop n}\right\}=0$ otherwise.

$\endgroup$
  • 1
    $\begingroup$ @almagest Stirling numbers of second kind. $\endgroup$ – drhab Dec 3 at 10:25
  • $\begingroup$ Ah, sorry. Yes, neat! $\endgroup$ – almagest Dec 3 at 10:26
  • $\begingroup$ @almagest Yup, curly braces are Stirling numbers of the second kind, and square brackets are for Stirling numbers of the first kind. $\endgroup$ – Matthew Daly Dec 3 at 10:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.