20.4: Regla de División

A veces es más fácil contar una colección relacionada pero más estructurada, donde la colección que realmente queremos contar corresponde a clases de equivalencia de la colección más estructurada.

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

Supongamos que\(\mathord{\equiv}\) es una relación de equivalencia en un conjunto finito\(A\) para que todas las clases de equivalencia tengan el mismo número de elementos. Entonces

\ begin {ecuación*}\ #\ {\ text {clases de equivalencia}\} =\ dfrac {\ vert A\ vert} {\ text {tamaño común de clases}}\ text {.} \ end {ecuación*} Es
decir,

\ begin {ecuation*}\ vert A/\ mathord {\ equiv}\ vert =\ dfrac {\ vert A\ vert} {\ vert [a]\ vert}\ text {,}\ end {ecuación*}
donde\(a\) es un elemento arbitrario de\(A\text{.}\)

Comprobante.

Escribir\(N\) para el número de clases de equivalencia, y escribir\(C\) para la cardinalidad común de las clases. Sabemos que las clases de equivalencia particionan el conjunto\(A\text{,}\) así que usando la Regla de Adición tenemos

\ begin {ecuation*}\ vert A\ vert =\ vert [a_1]\ vert +\ vert [a_2]\ vert +\ cdots +\ vert [a_n]\ vert\ text {,}\ end {equation*}
donde\(a_1, a_2, \ldots, a_N\) se encuentran un conjunto completo de representantes de clase de equivalencia. Pero hemos asumido que estas cardinalidades de clase son todas iguales entre sí, con cada clase satisfaciendo\(\vert [ a_j ] \vert = C\text{.}\) Así

\ begin {ecuación*}\ vert A\ vert =\ underbrackets {C + C +\ cdots + C} _ _ {N\ text {terms}} = N C\ text {,}\ end {ecuación*}
lo que lleva a

\ begin {ecuación*} N =\ dfrac {\ vert A\ vert} {C}\ text {,}\ end {ecuación*}
como se desee.

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

Vamos\(\Sigma = \{ \alpha, \beta, \gamma \}\text{.}\) ¿Cuántas palabras\(\Sigma^{\ast}_4\) contienen exactamente dos\(\alpha\) s, una\(\beta\) y una\(\gamma\text{?}\)

Solución

Escribir\(\Lambda\) para la colección de palabras en\(\Sigma^{\ast}_4\) del tipo descrito. En lugar de tratar de contar\(\Lambda\) directamente, considere la siguiente colección más estructurada.

Escribe\(\Sigma' = \{\alpha_1, \alpha_2, \beta, \gamma\}\text{,}\) y deja\(\Lambda'\) ser el conjunto de palabras en\(\Sigma'^\ast _4\) que no tengan letras repetidas. Similar a Ejemplo Trabajado 20.3.7, tenemos

\ begin {ecuación*}\ vert\ Lambda'\ vert = 4\ cdot 3\ cdot 2\ cdot 1 = 24\ texto {.} \ end {ecuación*}

Por cada par de estas palabras, escriba\(w_1 \equiv w_2\) si se mantienen las siguientes dos condiciones.

En cualquier posición que\(w_1\) contenga\(\alpha_1\text{,}\)\(w_2\) contiene cualquiera\(\alpha_1\) o\(\alpha_2\) en esa misma posición.
En cualquier posición que\(w_1\) contenga\(\alpha_2\text{,}\)\(w_2\) contiene cualquiera\(\alpha_1\) o\(\alpha_2\) en esa misma posición.
Puede verificar que\(\mathord{\equiv}\) define una relación de equivalencia en\(\Lambda'\text{.}\) Cada clase consta de exactamente dos palabras\(\{w_1,w_2\}\text{,}\) donde\(w_2\) tiene un\(\alpha_2\) where\(w_1\) tiene un\(\alpha_1\) y un\(\alpha_1\) where\(w_1\) tiene un\(\alpha_2\text{.}\) Por ejemplo, una clase de \(\Lambda' / \mathord{\equiv}\)es

\ begin {ecuación*} [\ alpha_1\ beta\ alpha_2\ gamma] =\ {\ alpha_1\ beta\ alpha_2\ gamma,\ alpha_2\ beta\ alpha_1\ gamma\}\ text {.} \ end {ecuación*}
Efectivamente, las clases eliminan la distinción entre\(\alpha_1\) y\(\alpha_2\text{,}\) para que bien puedan ser la misma letra, digamos,\(\alpha\text{.}\) En otras palabras, hay una correspondencia biyectiva entre las clases en\(\Lambda' / \mathord{\equiv}\) y las palabras en\(\Lambda\text{.}\) Usando el Regla de División, tenemos

\ begin {ecuation*}\ vert\ lambda\ vert =\ vert\ lambda'/\ mathord {\ equiv}\ vert =\ dfrac {\ vert\ Lambda'\ vert} {2} =\ dfrac {24} {2} = 12\ text {.} \ end {ecuación*}