# Stirling numbers and equivalence classes

The Stirling numbers $S(m,n)$ of second kind gives the number of ways a set with n elements can be partitioned into n disjoint nonempty sets.

I understand this, but in some books it is defined that,

they count the number of different equivalence relations with precisely $n$ equivalence classes that can be defined on an $m$ element set

Considering the example:

The set $\{1,2,3\}$ can be partitioned into 2 subsets in the following ways $$\{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{1\},\{2,3\}\}$$

why do we call these disjoint subsets as equivalence classes, what is the equivalence relation here ?

• The relation is pairs of elements (a, b) such that a and b appear in the same block of the partition. (You can verify that this is reflexive, symmetric, and transitive). Also, this may be helpful. en.wikipedia.org/wiki/… – Air Conditioner Dec 22 '17 at 18:48
• @Useless thanx. So does this mean that if you take any non-empty set and divide it into any number of disjoint subsets(partition) there has to be some kinda equivalence relation associated with it ?. thus we can call those disjoint subsets as equivalent classes – ss1729 Dec 22 '17 at 19:09
• Yes, if you have a partition (so your subsets are disjoint, nonempty, and their union is the original set), there a corresponding equivalence relation. – Air Conditioner Dec 22 '17 at 19:13
• @Useless thx.. i think that makes sense now. – ss1729 Dec 22 '17 at 19:15
• (Generally, there is a bijection between the set of equivalence relations and partitions, and thus if these sets are finite, counting partitions will also count equivalence relations.) – Air Conditioner Dec 22 '17 at 19:16

(The Fundamental Theorem of Equivalence Relations may be of interest.)

The relation is the pairs of elements $(x, y)$ such that x and y appear in the same block of the partition. Why does this work?

Let $P$ be a partition of a set $X$. Here's a sketch of why the relation $$\sim ~=~\{(x, y) \hspace{1pt}| \hspace{1pt} \text{x and y are in the same block of P} \}$$ $$\text{ (that is,} \text{ there is some } P_i \in P \text{ such that } x \in P_i \text{ and } y\in P_i )$$

is an equivalence relation.

From the definition of a partition, we know that for each $x \in X$, there is exactly one $P_i \in P$ such that $x \in P_i$.

First, let $x \in X$ be an element of the block $P_i \in P$. Since $x \in P_i$ and $x \in P_i$, $x\sim x$, and $\sim$ is reflexive.

Now, let $x \in X$ be an element of the block $P_i \in P$. If $x \sim y$ for some $y \in X$, then $y \in P_i$. Since $y \in P_i$ and $x\in P_i$, we have $y \sim x$, and $\sim$ is symmetric.

Last, we want to show if $x\sim y$ and $y \sim z$ for all $x, y, z \in X$, then $x \sim z$. Fix such an $x, y, z$. Let $x \in P_i$. Then $y \in P_i$, since $x \sim y$. Since $y \in P_i$, $y$ is only in the block $P_i$, and so for $y \sim z$ to be true, we must have $z \in P_i$. So $z \in P_i$. But since $x \in P_i$ and $z\in P_i$, we have $x\sim z$. Now forgetting we've fixed $x, y, z$, we've shown that $\sim$ is transitive.

Since we've shown $\sim$ is reflexive, symmetric, and transitive, it is an equivalence relation on $X$.

It can also be shown that the equivalence classes of an equivalence relation form a partition, and that the mapping sending each partition $P$ to the equivalence relation defined above is the mutual inverse of the mapping that maps an equivalence relation to the partition formed by its equivalence classes. The existence of these bijections means that if the sets of equivalence relations on a set $X$ and partitions of $X$ are finite, then the size of one is the size of the other.

Consider the possible equivalence relations on $[3] = \{1,2,3 \}$. (I will not write out reflexive & symmetric relations, & some transitive relations will be implied.) \begin{eqnarray*} 1 \nsim 2 \nsim 3 & \,\,\,\, & \{1\},\{2\},\{3\} \\ 1 \sim 2 \nsim 3 & \,\,\,\, & \{1,2\},\{3\} \\ 1 \nsim 2 \sim 3 & \,\,\,\, & \{1\}, \{2,3\} \\ 2 \nsim 1 \sim 3 & \,\,\,\, & \{1,3\},\{2\} \\ 1 \sim 2 \sim 3 & \,\,\,\, & \{1,2,3\} \\ \end{eqnarray*} It is hopefully clear from this that equivalence relations are in one to one correspondence with partitioning into disjoint unions.