Number of equivalence relations
Task number: 3395
Determine the number of distinct equivalence relations on five elements.
Hint
Represent each equivalence relation as a family of sets.
Solution
On five elements there are the following equivalence relations:
– one with one equivalence class
– five with two equivalence classes of size 4 and 1.
– ten with two equivalence classes of size 3 and 2.
– ten with three equivalence classes of size 3, 1 and 1.
– fifteen with three equivalence clases of size 2, 2 and 1.
– ten with four equivalence classes of size 2, 1, 1 and 1.
– one with five single-element equivalence classes.Answer
We can construct 52 distinct equivalence relations on five elements.
