Question

How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements ?

Answer 1

Answer:

Mark me as brainliest please

Step-by-step explanation:

As equivalence relations on a set E={1,2,3,4,5} is completely determined by the partition of E given by the equivalence classes of E, we first count the partitions of E, with |E|=5, into 3 nonempty subsets.

Let P(n,k) denote the set of all unordered partitions of an n-set into k partition blocks, which are all non empty by definition. The number of all such partitions, i.e. |P(n,k)| is called the Stirling number S(n,k) of second kind. These numbers satisfy the recurrence relation:

S(n,k) = S(n-1,k-1) + kS(n-1,k)…………(1).

This is proved by means of the following combinatorial argument. Suppose that we write an n-set A as the disjoint union of an (n-1)-set B and a particular singleton subset {a} of A. Then every k-partition of A can either be obtained from a (k-1)-partition of B by adding {a} as the k_th block or else, by including the element 'a' to each of the existing k partition blocks of B.

Now we may evaluate S(5,3) using the recurrence relation (1), staring from

S(n,1)=1, S(n,n)=1 and S(n,0)=0. Thus

S(5,3) = S(4,2)+3.S(4,3),

S(4,3) = S(3,2)+3.S(3,3),

S(4,2) = S(3,1)+2.S(3,2),

S(3,2) = S(2,1)+2.S(2,2) = 1+ 2×1 = 3. Working backwards, we get

S(4,2) = 1 + 2×3 = 7.

S(4,3) = 3 + 3×1 = 6.

S(5,3) = 7 + 3×6 = 25.

If E = (W_1) U (W_2) U ……(W_k) is a partition of E, then the equivalence relation R whose equivalence classes are the above blocks, is nothing but

R = U(j=1 to k)[(W_j)×(W_j)].

Thus the number of equvalence relations on the 5-set E, with exactly 3 equivalence classes is S(5,3) = 25.