20.4: Division Rule

Sometimes it is easier to count a related but more structured collection, where the collection we actually want to count corresponds to equivalence classes of the more structured collection.

Theorem \(\PageIndex{1}\): Division Rule

Suppose \(\mathord{\equiv}\) is an equivalence relation on a finite set \(A\) so that the equivalence classes all have the same number of elements. Then

\begin{equation*} \# \{ \text{equivalence classes} \} = \dfrac{\vert A \vert}{\text{common size of classes}} \text{.} \end{equation*}
That is,

\begin{equation*} \vert A / \mathord{\equiv} \vert = \dfrac{\vert A \vert}{ \vert [ a ] \vert} \text{,} \end{equation*}
where \(a\) is an arbitrary element of \(A\text{.}\)

Proof.

Write \(N\) for the number of equivalence classes, and write \(C\) for the common cardinality of the classes. We know that the equivalence classes partition the set \(A\text{,}\) so using the Addition Rule we have

\begin{equation*} \vert A \vert = \vert [a_1 ] \vert + \vert [a_2 ] \vert + \cdots + \vert [ a_N ] \vert \text{,} \end{equation*}
where \(a_1, a_2, \ldots, a_N\) are a complete set of equivalence class representatives. But we have assumed that these class cardinalities are all equal to each other, with each class satisfying \(\vert [ a_j ] \vert = C\text{.}\) So

\begin{equation*} \vert A \vert = \underbrace{C + C + \cdots + C}_{N \text{ terms}} = N C \text{,} \end{equation*}
which leads to

\begin{equation*} N = \dfrac{\vert A \vert}{C} \text{,} \end{equation*}
as desired.

Example \(\PageIndex{1}\): Equivalent Words.

Let \(\Sigma = \{ \alpha, \beta, \gamma \}\text{.}\) How many words in \(\Sigma^{\ast}_4\) contain exactly two \(\alpha\)s, one \(\beta\) and one \(\gamma\text{?}\)

Solution

Write \(\Lambda\) for the collection of words in \(\Sigma^{\ast}_4\) of the type described. Instead of trying to count \(\Lambda\) directly, consider the following more structured collection.

Write \(\Sigma' = \{\alpha_1, \alpha_2, \beta, \gamma\}\text{,}\) and let \(\Lambda'\) be the set of words in \(\Sigma'^\ast _4\) that have no repeated letters. Similar to Worked Example 20.3.7, we have

\begin{equation*} \vert \Lambda' \vert = 4 \cdot 3 \cdot 2 \cdot 1 = 24 \text{.} \end{equation*}

For each pair of these words, write \(w_1 \equiv w_2\) if the following two conditions hold.

At whatever position \(w_1\) contains \(\alpha_1\text{,}\) \(w_2\) contains either \(\alpha_1\) or \(\alpha_2\) at that same position.
At whatever position \(w_1\) contains \(\alpha_2\text{,}\) \(w_2\) contains either \(\alpha_1\) or \(\alpha_2\) at that same position.
You may check that \(\mathord{\equiv}\) defines an equivalence relation on \(\Lambda'\text{.}\) Each class consists of exactly two words \(\{w_1,w_2\}\text{,}\) where \(w_2\) has an \(\alpha_2\) where \(w_1\) has an \(\alpha_1\) and an \(\alpha_1\) where \(w_1\) has an \(\alpha_2\text{.}\) For example, one class of \(\Lambda' / \mathord{\equiv}\) is

\begin{equation*} [ \alpha_1 \beta \alpha_2 \gamma ] = \{ \alpha_1 \beta \alpha_2 \gamma, \alpha_2 \beta \alpha_1 \gamma \} \text{.} \end{equation*}
Effectively, the classes remove the distinction between \(\alpha_1\) and \(\alpha_2\text{,}\) so that they might as well be the same letter, say, \(\alpha\text{.}\) In other words, there is a bijective correspondence between the classes in \(\Lambda' / \mathord{\equiv}\) and the words in \(\Lambda\text{.}\) Using the Division Rule, we have

\begin{equation*} \vert \Lambda \vert = \vert \Lambda' / \mathord{\equiv} \vert = \dfrac{\vert \Lambda' \vert}{2} = \dfrac{24}{2} = 12 \text{.} \end{equation*}