Question

Find the number of equivalence relations that can be defined on a set of 6 elements.

Answer 1

Answer on Question #81206 – Math – Discrete Mathematics

Question

Find the number of equivalence relations that can be defined on a set of 6 elements.

Solution

The number to find is the number of different partitions of a set of 6 elements into equivalence classes.

Let $A_n$ denote the number of partitions for a set of $n$ elements. We need to find $A_6$.

We will find a recursive formula for $A_n$. First, $A_0 = 1$ (no elements, one way), $A_1 = 1$ (one element, one way).

For the set of $n$ element take one particular element. There are the following possibilities:

- this element is not equivalent to any other – there will be $A_{n-1}$ such partitions (we take any partition of other $n-1$ elements and add a class with this one particular element to it)

- this element is in equivalence class with exactly one other element – there are $\binom{n-1}{1}$ ways to choose this element and $A_{n-2}$ partitions of all other elements corresponding to each choice, totally $\binom{n-1}{1}A_{n-2}$ partitions

- this element is in equivalence class with exactly two other elements – there are $\binom{n-1}{2}$ ways to choose these elements and $A_{n-3}$ partitions of all other elements corresponding to each choice, totally $\binom{n-1}{2}A_{n-3}$ partitions

...

- this element is in equivalence class with all other elements – there are $\binom{n-1}{n-1}$ ways to choose these other elements and $A_0$ partitions of all other elements corresponding to each choice, totally $\binom{n-1}{n-1}A_0 = 1$ partitions

Thus, the formula is

$$A_n = A_{n-1} + \binom{n-1}{1} A_{n-2} + \binom{n-1}{2} A_{n-3} + \ldots + \binom{n-1}{n-2} A_1 + A_0$$

It follows from the formula that

$$A_2 = A_1 + A_0 = 2,$$ $$A_3 = A_2 + 2A_1 + A_0 = 2 + 2 \cdot 1 + 1 = 5,$$ $$A_4 = A_3 + 3A_2 + 3A_1 + A_0 = 5 + 3 \cdot 2 + 3 \cdot 1 + 1 = 15,$$ $$A_5 = A_4 + 4A_3 + 6A_2 + 4A_1 + A_0 = 15 + 4 \cdot 5 + 6 \cdot 2 + 4 \cdot 1 + 1 = 52$$ $$A _ {6} = A _ {5} + 5 A _ {4} + 1 0 A _ {3} + 1 0 A _ {2} + 5 A _ {1} + A _ {0} = 5 2 + 5 \cdot 1 5 + 1 0 \cdot 5 + 1 0 \cdot 2 + 5 \cdot 1 + 1 = 2 0 3.$$

Answer: 203 equivalence relations.

Answer provided by https://www.AssignmentExpert.com