Number of equivalence relations with a fixed size

Question

How can I find the number of equivalence relations R on a set of size 7 such that |R|=29?

Any advice would be greatly appreciated! :D

Answer 1

HINT: Let $A$ be the set of size $7$. Think about the partition corresponding to the equivalence relation $R$. Suppose that it has parts $P_1,\ldots,P_n$ of sizes $m_1,\ldots,m_n$, respectively. For each $k=1,\ldots,n$, the part $P_k$ contributes $m_k^2$ ordered pairs to $R$. (Why?) Thus, we want

$$29=|R|=\sum_{k=1}^nm_k^2\;,$$

where we know that $$\sum_{k=1}^nm_k=7\;.$$

In other words, we need to find sets of integers summing to $7$ whose squares sum to $29$. One obvious set is $\{2,5\}$: $2+5=7$, and $2^2+5^2=29$. I leave you to check whether there are any others.

Now consider the partitions that have two classes, one of size $2$ and the other of size $5$. How many of them are there? Note that once you decide which $2$ elements of $A$ are in one class, you know exactly which $5$ are in the other class.

Answer 2

since equivalence relation is reflexive, 7 components are already in R. Remaining pairs are 22 therefore, and they are symmetric 11 x 2.

dividing in equivalence classes means basically grouping elements where all elements are connected, equivalence to each other in the group.

• group with 1 member has 0 pairs (excl. reflexives)
• group with 2 members {a,b} has 2 pairs: (excl. reflexives)
• group with 3 members has 6 pairs. (excl. reflexives)
• group with 4 members has 12 pairs. (excl. reflexives)
• group with 5 members has 20 pairs. (excl. reflexives)

there shouldn't be 6 or more members in an equivalence class since pairs are more than 22. consider combinations of 20, 12, 6, 2 how than can sum up till 22, but dont forget that you have 7 elements only.

There is only one option according to theses calculations (not considering other isomorphic equivalence relations).

Answer 3

Hints: An equivalence relation must be reflexive, symmetric, and transitive.

Reflexivity requires that we include $(x,x)$ for each $x$ in our set; that accounts for $7$ ordered pairs in $R$, leaving us $22$ to work with.

Now, all remaining pairs are of the form $(x,y)$ where $x\neq y$. But, whenever we include $(x,y)$ with $x\neq y$, we must also include the (distinct!) pair $(y,x)$, in order to be symmetric. So, we need to choose $11$ unordered pairs $\{x,y\}$ of distinct elements, and place both $(x,y)$ and $(y,x)$ in $R$.

So, what you really need to count here is how many ways you can choose these $11$ unordered pairs of elements such that transitivity is preserved -- that is, whenever we include the unordered pairs $\{x,y\}$ and $\{y,z\}$, where $x,y,z$ are distinct, we must also include the unordered pair $\{x,z\}$.

From here, my suggestion is to think about the equivalence classes on your set (call it $X$) induced by $R$. If an equivalence class consists of the elements $x_1,\ldots,x_n$, then $(x_i,x_j),(x_j,x_i)\in R$ for every $i\neq j$. Further, there are no relations $(x,y)$ between elements in different equivalence classes.

An equivalence class of size $1$ doesn't account for any new elements of $R$.

An equivalence class of size $2$ (say $\{x,y\}$) requires two relations, $(x,y)$ and $(y,x)$.

An equivalence class $\{x,y,z\}$ requires that we insert $(x,y)$, $(y,x)$, $(x,z)$, $(z,x)$, $(y,z)$, and $(z,y)$, for six total relations. And so on. Can you find a formula for the number of relations required to account for an equivalence class of size $n$?

The total number of relations (other than the reflexive relations $(x,x)$, ...) is just the sum of the number of relations required for each of its equivalence classes. So, you need to find a formula for how many relations are required to have $k$ equivalence classes of sizes $n_1,\ldots,n_k$, and figure out how to make this $22$.

Answer 4

Hint:

If $\cal R$ is a solution , let $k$ the number of cosets: then if $n_1,...,n_k$ are numbers of elements of theses cosets we have :$$|R|=29 = n_1^2 + \cdots + n_k^2$$ the maximum value of $k$ is $7$ who corresponds to the trivial equivalence having $7$ cosets.

we have $n_1 \leq 5$ because $6^2=36 > 29$.

If $n_1=5$ then $n_1^2=25$ this gives $2$ cosets with $5$ elements for the firts end $2$ for the second. The number of theses solutions is : $\binom{7}{5}=\binom 72 = 21$

You can discuss the others caes like this .. you can simplify the discussion by giving the minimum and maximum value of $n_k$ using:

$$\sum_{i=1}^k n_i= 7,\sum_{i=1}^k n_i^2= 29 ,k \min(n_i) \leq 7 \leq k \max (n_i),k \min(n_i^2) \leq 29 \leq k \max (n_i^2)$$

Answer 5

I'm doing the same homework as User110064.

So, if I have understood this correctly, the number 7 can be partitioned in 15 different ways:

7, 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 4+1+1+1, 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 2+1+1+1+1+1+1, 1+1+1+1+1+1+1+1

And the only partition satisfying that the squared sum of the elements equals 29 is 5+2. Hence, the number of equivalence relations R on the set (of size 7) such that |R|=29 is one. Is this correct?