# How many equivalence relations are there on $\{a,b,c,d,e,f\}$ with $3$ equivalence classes? [closed]

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.

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

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.

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.

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