Let . Consider the set
Then the number of elements in is ___.
Concepts Used
A relation on a set is an equivalence relation if it is reflexive, symmetric and transitive.
Every equivalence relation splits into disjoint equivalence classes , and conversely every such partition gives exactly one equivalence relation: .
If the classes have sizes , then and .
To count partitions, choose the classes one after another using . If classes have the same size, divide by , because the classes are unordered.
Approach: (i) find every list of class sizes with and ; (ii) count the ways to split into classes of each such list; (iii) add the counts.
Step 1: Why is a sum of squares
Two elements are related exactly when they lie in the same class. A class with elements contributes all ordered pairs formed from its own elements, and no pair joins two different classes. Hence
For example, on the classes give
Step 2: Translate the condition
We need class sizes with
Feasibility check: subtracting the two equations in (1),
contains the diagonal pairs , and its other pairs come in symmetric couples . So exactly unordered pairs with are related. Since is even, such a relation can exist.
Step 3: Bound the largest class
Upper bound: , so no class has or more elements, i.e. .
Lower bound: if every class had at most elements, then for each , so
which is impossible. Hence , and so .
Step 4: Find every admissible list of class sizes
Case : the other classes hold elements and need as the sum of their squares.
Only works, giving class sizes .
Case : the other classes hold elements and need as the sum of their squares (a part of is impossible, as ).
Only works, giving class sizes . So exactly two types of equivalence relation have elements:
Step 5: Count the relations of each type
Each partition of with the required class sizes gives exactly one relation in , so we count partitions. Fill the classes of different sizes first; the leftover elements then fall into place and nothing is counted twice.
Type I : choose the six-element class, then the pair; the two leftover elements are the singletons.
Cross-check: picking the singletons one at a time counts each partition twice, so divide by :
Type II : all three sizes differ. Choose the five-element class, then the four-element class; the last element is the singleton.
Cross-check: choosing the singleton first, .
Tagged Combinations and selections with conditions. Machine-assigned, so read it as a strong shortlist rather than a verdict.