Skip to main content
Mathematics LibreTexts

20.4: Division Rule

  • Page ID
    83508
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

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


    This page titled 20.4: Division Rule is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.