20.2: Reglas de suma y resta
- Page ID
- 118086
Como es habitual en matemáticas, romper un gran problema en partes más pequeñas es una estrategia útil.
Supongamos que\(U\) es un conjunto finito.
- Si\(U = A_1 \sqcup A_2\text{,}\) entonces\(\vert U \vert = \vert A_1 \vert + \vert A_2 \vert\text{.}\)
- 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.
El enunciado 1 del Teorema se\(\PageIndex{1}\) puede extender a una unión disjunta de cualquier número de subconjuntos.
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.
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{.}\)
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*}