20.2: Reglas de suma y resta

Como es habitual en matemáticas, romper un gran problema en partes más pequeñas es una estrategia útil.

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

Supongamos que\(U\) es un conjunto finito.

1. Si\(U = A_1 \sqcup A_2\text{,}\) entonces\(\vert U \vert = \vert A_1 \vert + \vert A_2 \vert\text{.}\)
2. Si\(U = A_1 \cup A_2\text{,}\) entonces\(\vert U \vert = \vert A_1 \vert + \vert A_2 \vert - \vert A_1 \cap A_2 \vert\text{.}\)

Idea de Prueba.

Después de recordar la definición de unión disjunta, la Declaración 1 debería ser obvia. Para acreditar la Declaración 2, aplicar la Declaración 1 a los siguientes sindicatos disjuntos:

\ begin {alinear*} U & = A_1\ sqcup (A_2\ setmenos A_1), & A_2 & = (A_2\ setmenos A-1)\ sqcup (A_1\ cap A_2). \ end {align*}
Luego combine las igualdades resultantes de cardinalidades.

Comentario\(\PageIndex{1}\)

El enunciado 1 del Teorema se\(\PageIndex{1}\) puede extender a una unión disjunta de cualquier número de subconjuntos.

Ejemplo\(\PageIndex{1}\): Counting by breaking into cases.

Cuántas palabras de longitud\(3\) o menos hay usando alfabeto\(\Sigma = \{ \alpha, \omega \}\text{?}\)

Solución

Escribe\(\Sigma ^{\ast}_{\le 3}\) para significar el conjunto de palabras en alfabeto\(\Sigma\) de longitud\(3\) o menos. Entonces

\ begin {ecuation*}\ Sigma ^ {\ ast} _ {\ le 3} =\ Sigma ^ {\ ast} _0\ sqcup\ Sigma ^ {\ ast} _1\ sqcup\ Sigma ^ {\ ast} _2\ sqcup\ Sigma ^ {\ ast} _3\ text {,}\ end {ecuación*}
para que podamos romper en casos basados en la longitud y luego aplicar la Regla de Adición.

Contar\(\Sigma ^{\ast}_0\).
Sólo hay una palabra de longitud\(0\text{:}\) la palabra vacía. Entonces\(\vert \Sigma ^{\ast}_0 \vert = 1\text{.}\)

Contar\(\Sigma ^{\ast}_1\).
Solo hay dos palabras de longitud\(1\text{:}\) las palabras de una sola letra\(w_\alpha = \alpha\) y\(w_\omega = \omega\text{.}\) Así\(\vert \Sigma ^{\ast}_1 \vert = 2\text{.}\)

Contar\(\Sigma ^{\ast}_2\).
Podemos contar simplemente enumerando los elementos:

\ begin {ecuación*}\ Sigma ^ {\ ast} _2 =\ {\ alfa\ alfa,\ alfa\ omega,\ omega\ alfa,\ omega\ omega\}\ texto {.} \ end {equation*}
Entonces\(\vert \Sigma ^{\ast}_2 \vert = 4\text{.}\)

Contar\(\Sigma ^{\ast}_3\).
Esta vez solo usaremos el razonamiento inductivo. Cada palabra en\(\Sigma ^{\ast}_2\) puede extenderse a una palabra en\(\Sigma ^{\ast}_3\) agregando una\(\alpha\) o una\(\omega\) al final. Entonces debe haber el doble de palabras en\(\Sigma ^{\ast}_3\) como en\(\Sigma ^{\ast}_2\text{,}\) i.e.\(\vert \Sigma ^{\ast}_3 \vert = 8\text{.}\)

Conteo total.
Usando la Regla de Adición, obtenemos el total sumando nuestros resultados preliminares:

\ begin {ecuación*}\ vert\ Sigma ^ {\ ast} _ {\ le 3}\ vert = 1 + 2 + 4 + 8 = 15\ text {.} \ end {ecuación*}

Otra estrategia común en matemáticas es considerar lo contrario.

Teorema\(\PageIndex{2}\): Subtraction Rule.

Supongamos que\(U\) es un conjunto finito. Por cada subconjunto\(A \subseteq U\text{,}\) que tenemos\(\vert A \vert = \vert U \vert - \vert A^C \vert \text{.}\)

Idea de Prueba.

Ya que siempre\(U = A \sqcup A^C \) es cierto, simplemente aplique la Declaración 1 del Teorema 20.2.1 a esta unión disjunta y reordene para aislar\(\vert A \vert\text{.}\)

Ejemplo\(\PageIndex{2}\): Counting by counting the complement.

Para alfabeto\(\Sigma = \{a, b, c, \ldots, y, z\} \text{,}\) cuántas palabras en\(\Sigma ^{\ast}_2\) no empiezan por la letra\(\mathrm{a}\text{?}\) Es mucho más fácil contar el número de palabras en las\(\Sigma ^{\ast}_2\) que sí empiezan\(\mathrm{a}\text{,}\) ya que solo hay\(26\) posibilidades para la segunda letra.

Más adelante en este capítulo aprenderemos una regla que nos permitirá calcular fácilmente el número total de palabras en\(\Sigma ^{\ast}_2\) ser\(26^2\) (ver Ejemplo Trabajado 20.3.6). Aceptando este hecho por el momento, entonces podemos usar la Regla de Resta para calcular

\ begin {alinear*}\ #\ {2\ texto {-letras palabras que no empiezan con}\ mathrm {a}\} & =\ vert\ Sigma ^ {\ ast} _2\ vert -\ #\ {2\ texto {-letras palabras que comienzan con}\ mathrm {a}\}\\ & = 26^2 - 26\\ & = 26 (26 - 1)\\ & = 26\ cdot 25\ texto {.} \ end {align*}