20.3: Regla de multiplicación
- Page ID
- 118115
\(\vert A \times B \vert\)Para qué sirve\(A = \{ 0, 1, 2, 3 \}\) y\(B = \{ -1, 0, 1 \}\text{?}\)
Solución
Podemos resolver esto con solo escribir los elementos de\(A \times B\) y contarlos.
\ begin {alinear*} A\ veces B & =\ {(0, -1), (0,0), (0,1), (1, -1), (1,0), (1,1),\\ &\ quad (2, -1), (2,0), (2,1), (3, -1), (3,0), (3,1)\}\ end {align*}
Así\(\vert A \times B \vert = 12\text{.}\)
\(\vert C \times D \vert\)Para qué sirve\(C = \{ a,b,c,\ldots,z \}\) y\(D = \{0,1,2,\cdots,99 \}\text{?}\)
Solución
Escribir todos los elementos de\(C \times D\) y luego contarlos todos parece mucho trabajo. En cambio, usando nuestra experiencia de Ejemplo Trabajado\(\PageIndex{1}\), observe que solemos realizar la tarea de escribir los elementos de un producto cartesiano en un patrón para asegurarnos de que los obtenemos todos. Uno por uno escogemos un solo elemento del primer conjunto\(C\text{,}\) y lo emparejamos con cada elemento del segundo conjunto\(D\text{.}\) A partir de este patrón vemos que para cada uno\(c \in C\text{,}\) hay\(\vert D \vert\) elementos de\(C \times D\) con\(c\) como la primera coordenada, y hay\(\vert C \vert\) tales agrupaciones de elementos de\(C \times D\text{.}\) Así llegamos a
\ begin {ecuación*}\ vert C\ veces D\ vert =\ vert C\ vert\ cdot\ vert D\ vert = 26\ cdot 100 = 2600\ text {.} \ end {ecuación*}
Para conjuntos\(X\) y\(Y\text{,}\) definir una relación de equivalencia sobre\(X \times Y\) cuyas clases de equivalencia\(X \times Y\) particionan de la manera descrita en la solución proporcionada a Ejemplo Trabajado\(\PageIndex{2}\). Luego describa cómo corresponde el número de clases y el número de objetos en cada clase\(\vert X \vert\) y\(\vert Y \vert\text{.}\)
Si hay\(m\) formas de realizar la tarea\(S\) y\(n\) formas de realizar la tarea\(T\text{,}\), entonces hay\(m n\) formas de realizar la tarea\(S\) seguida de la tarea\(T\text{.}\)
Advertencia\(\PageIndex{1}\)
La Regla de Multiplicación solo se aplica a tareas consecutivas de\(S,T\) manera que el número de formas de realizar la tarea\(T\) sea independiente de la elección que se haga al realizar la tarea\(S\text{.}\)
Para crear un ejemplo específico de un elemento a partir de primero\(A \times B\text{,}\) debemos elegir un elemento de\(A\) para ser la primera coordenada (tarea\(S\)), luego elegir un elemento de\(B\) para ser la segunda coordenada (tarea\(T\)). Hay\(m = \vert A \vert\) formas de realizar la tarea\(S\) y\(n = \vert B \vert\) formas de realizar la tarea\(T\text{.}\) Por lo tanto, la Regla de Multiplicación dice que hay\(m n\) formas de construir un elemento del\(A \times B\text{,}\) cual significa\(\vert A\times B \vert = m n\text{.}\)
Supongamos que eres un director de casting y necesitas seleccionar tanto a un actor principal como a un suplente para el papel principal en una obra de teatro. Si\(n\) los actores hacen una audición para el papel, entonces hay\(n\) diferentes formas de seleccionar al actor principal. Una vez realizada esta elección, quedan\(n-1\) diferentes formas de seleccionar al suplente. De ahí que haya\(n (n - 1)\) formas de emitir el papel.
Ahora, el grupo real de candidatos a suplente diferirá en función de a qué actor se le ofrezca el papel principal. No obstante, no importa a quién se elija para el liderato, el número de candidatos restantes para suplente es el mismo.
Podemos extender la Regla de Multiplicación a cualquier número (finito) de tareas consecutivas.
Si\(A_1,A_2,\ldots,A_m\) son conjuntos finitos con\(\vert A_j \vert= m_j\text{,}\) entonces
\ begin {ecuation*}\ vert A-1\ times A_2\ times\ cdots\ times A_\ ell\ vert = m_1 m_2\ cdots m_\ ell\ text {.} \ end {ecuación*}
Recordemos que, dado alfabeto\(\Sigma\) y número\(n \in \mathbb{N} \text{,}\)\(\Sigma^\ast_n\) es el conjunto de palabras de longitud\(n\text{.}\) Si\(\vert \Sigma \vert= m\text{,}\) lo que es\(\vert \Sigma^\ast_n \vert\text{?}\)
Solución
Para construir una palabra de ejemplo específica\(w \in \Sigma^\ast_n\text{,}\) hay:
- \(m\)formas de elegir la primera letra,
- \(m\)formas de elegir la segunda letra,
- ...,
- \(m\)formas de elegir la\(n^{th}\) letra.
Así que hay
\ begin {ecuación*}\ underbrackets {m\ cdot m\ cdot m\ cdot\ cdot\ cdots\ cdot m} _ {n\ text {factors}} = m^n\ end {ecuación*}
formas de construir\(w\text{.}\) Concluimos\(\vert \Sigma^\ast_n \vert = m^n\text{.}\)
Supongamos\(\vert \Sigma \vert = 5\text{.}\) ¿Cuántas palabras en no\(\vert \Sigma^\ast_5 \vert\) tienen letras repetidas? (Es decir, ¿en el que no hay dos letras iguales?)
Solución
Para construir una palabra de ejemplo específica\(w \in \Sigma^\ast_5\) en la que no hay dos letras iguales, hay
- \(5\)formas de elegir la primera letra,
- \(4\)formas restantes de elegir la segunda letra,
- \(3\)restantes formas de elegir la tercera letra,
- \(2\)formas restantes de elegir la cuarta letra, y
- sólo\(1\) queda manera de elegir la última letra.
Así que hay
\ begin {ecuación*} 5\ cdot 4\ cdot 3\ cdot 2\ cdot 1 = 120\ end {ecuación*}
formas de construir\(w\text{.}\)
Similar a Ejemplo\(\PageIndex{4}\), mientras que el conjunto real de candidatos para la siguiente letra en cada paso diferirá en función de qué letras ya se han elegido, el número de letras restantes siempre es independiente de qué letras se han elegido realmente hasta ahora. Entonces la Regla de Multiplicación se puede aplicar a este problema exactamente como la hemos aplicado.
Vamos\(\Sigma = \{a, b, c, \ldots, y, z \} \text{.}\) ¿Cuántos palíndromos\(w\) con\(3 \le \vert w \vert \le 6\) hay en\(\Sigma^\ast\text{?}\)
Solución
Romper en casos en función de la duración de\(w\text{.}\)
Caso\(\vert w \vert = 3\).
Una vez que elegimos la primera letra, la última se elige para nosotros, pero seguimos siendo libres de elegir la letra media. Entonces hay\(26^2\) palíndromos de longitud\(3\text{.}\)
Caso\(\vert w \vert = 4\).
Una vez que elegimos las dos primeras letras, las dos últimas son elegidas para nosotros. Por lo que también hay\(26^2\) palíndromos de longitud\(4\text{.}\)
Caso\(\vert w \vert = 5\).
Una vez que elegimos las dos primeras letras, las dos últimas son elegidas para nosotros, pero seguimos siendo libres de elegir la letra media. Entonces hay\(26^3\) palíndromos de longitud\(5\text{.}\)
Caso\(\vert w \vert = 6\).
Una vez que elegimos las tres primeras letras, las últimas tres son elegidas para nosotros. Por lo que también hay\(26^3\) palíndromos de longitud\(6\text{.}\)
Total.
Aplicando la Regla de Adición a estos casos no superpuestos, obtenemos
\ begin {align*} 26^2 + 26^2 + 26^3 + 26^3 & = 26^2 (1+1+26+26)\\ & = 54\ cdot 26^2\\ & = 36.504\ end {alinear*}
como el número de palíndromos longitud\(3\) hasta\(6\text{.}\)
Set\(A = \{a,b,c\}\) y\(B = \{0,1,2,3,4\}\text{.}\) ¿Cuántas funciones\(A \to B\) existen? ¿Cuántas de estas son inyecciones? ¿Cuántas son las sobreyecciones?
Solución
Número de funciones.
Una función se\(f: A \rightarrow B\) puede construir en tres pasos: elegir\(f(a)\text{,}\) luego elegir\(f(b)\text{,}\) luego elegir\(f(c)\text{.}\) Cada uno de los pasos se puede llevar a cabo de\(\vert B \vert = 5\) maneras. Entonces el número de funciones es\(5^3 = 125\text{.}\)
Número de inyecciones.
Una inyección se\(f: A \hookrightarrow B\) puede construir en tres pasos: elija\(f(a)\text{,}\) luego elija\(f(b)\) ser diferente de\(f(a)\text{,}\) luego elija\(f(c)\) ser diferente de ambos\(f(a)\) y El\(f(b)\text{.}\) primer paso tiene\(\vert B \vert = 5\) opciones. El segundo paso tiene\(\vert B \setminus \{f(a)\} \vert = 4\) opciones. El tercer paso tiene\(\vert B \setminus \{f(a),f(b)\} \vert = 3\) opciones. Entonces el número de inyecciones es\(5 \cdot 4 \cdot 3 = 60\text{.}\)
- Una mirada hacia adelante.
-
Observe que el número de inyecciones ha resultado ser
\ comenzar {ecuación*}\ dfrac {\ vert B\ vert!} {(\ vert B\ vert -\ vert A\ vert)!} \ texto {.} \ end {equation*}
Entenderemos mejor cómo surge esta fórmula en la Sección 21.4.
Número de sobrejecciones.
Supongamos\(f: A \rightarrow B\text{.}\) Dado\(\vert A \vert = 3\text{,}\) que lo más grande que\(\vert f(A)\vert\) puede ser es el\(3\text{,}\) que ocurre cuando\(f\) es inyectable. Sin embargo, incluso en un caso tan grande es aún más pequeño entonces\(\vert B \vert\text{,}\) por lo que no existen suryecciones. Es decir, el número de surjecciones es\(0\text{.}\)