EF Division rule

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*}

where \(a_1, a_2, \dotsc, 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 \(\card{\eqclass{a_j}} = C \text{.}\) So

\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*}