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