Section 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 20.4.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*}
\ncardop \{ \text{equivalence classes} \} = \frac{\card{A}}{\text{common size of classes}} \text{.}
\end{equation*}
That is,
\begin{equation*}
\card{A / \mathord{\equiv}} = \frac{\card{A}}{\card{\eqclass{a}}} \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*}
\card{A} = \card{\eqclass{a_1}} + \card{\eqclass{a_2}} + \dotsb + \card{\eqclass{a_N}} \text{,}
\end{equation*}
\begin{equation*}
\card{A} = \underbrace{C + C + \dotsb + C}_{N \text{ terms}} = N C \text{,}
\end{equation*}
which leads to
\begin{equation*}
N = \frac{\card{A}}{C} \text{,}
\end{equation*}
as desired.
Worked Example 20.4.2. Equivalent words.
Let \(\Sigma = \{ \alpha, \beta, \gamma \}\text{.}\) How many words in \(\words{\Sigma}_4\) contain exactly two \(\alpha\)s, one \(\beta\) and one \(\gamma\text{?}\)
Solution.
Write \(\Lambda\) for the collection of words in \(\words{\Sigma}_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
\(\words{(\Sigma')}_4\) that have no repeated letters. Similar to
Worked Example 20.3.11, we have
\begin{equation*}
\card{\Lambda'} = 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*}
\eqclass{\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*}
\card{\Lambda} = \card{\Lambda' / \mathord{\equiv}} = \frac{\card{\Lambda'}}{2} = \frac{24}{2} = 12 \text{.}
\end{equation*}
