1.6: Recuento avanzado usando PIE

Template:MathJaxLevin

¡Investiga!

Tienes 11 mini tartas idénticas de lima con llave para regalar a 4 niños. Sin embargo, no quieres que ningún niño consiga más de 3 pasteles. ¿De cuántas formas puedes distribuir las tartas?

1. ¿Cuántas formas hay de distribuir las tartas sin restricción alguna?
2. Vamos a deshacernos de las formas en que uno o más niños obtienen demasiadas tartas. ¿Cuántas formas hay de distribuir las tartas si Al obtiene demasiadas tartas? ¿Y si Bruce recibe demasiados? ¿O Cat? ¿O Dent?
3. ¿Y si a dos niños les dan demasiadas tartas? ¿De cuántas maneras puede suceder esto? ¿Importa a qué dos niños escojas para sobrealimentar?
4. ¿Es posible que a tres niños les den demasiadas tartas? Si es así, ¿de cuántas formas puede suceder esto?
5. ¿Cómo debes combinar todos los números que encontraste arriba para responder a la pregunta original?

Supongamos que ahora tienes 13 tartas y 7 hijos. Ningún niño puede tener más de 2 tartas. ¿De cuántas formas puedes distribuir las tartas?

Estrellas y barras nos permite contar el número de formas de distribuir 10 cookies a 3 niños y soluciones numéricas naturales\(x+y+z = 11\text{,}\) para por ejemplo. Una modificación relativamente fácil nos permite poner una restricción de límite inferior a estos problemas: tal vez cada niño deba obtener al menos dos cookies o\(x,y,z \ge 2\text{.}\) Esto se hizo asignando primero a cada niño (o variable) 2 cookies (o unidades) y luego distribuyendo el resto usando estrellas y barras.

¿Y si quisiéramos una restricción de límite superior? Por ejemplo, podríamos insistir en que ningún niño obtenga más de 4 galletas o\(x, y, z \le 4\text{.}\) que resulte que esto es considerablemente más difícil, pero aún posible. La idea es contar todas las distribuciones y luego eliminar aquellas que violen la condición. Es decir, debemos contar la cantidad de formas de distribuir 11 galletas a 3 niños en las que uno o más de los niños obtienen más de 4 cookies. Para cualquier niño en particular, esto no es un problema; lo hacemos usando estrellas y barras. Pero, ¿cómo combinar el número de formas para el niño A, o B o C? Debemos usar el PIE.

El Principio de Inclusión/Exclusión (PIE) da un método para encontrar la cardinalidad de la unión de conjuntos no necesariamente disjuntos. Vimos en Subsección cómo funciona esto con tres conjuntos. Para encontrar cuántas cosas hay en uno o más de los sets\(A\text{,}\)\(B\text{,}\) y solo\(C\text{,}\) debemos sumar el número de cosas en cada uno de estos conjuntos. Sin embargo, si hay algún solapamiento entre los conjuntos, esos elementos se cuentan varias veces. Entonces restamos las cosas en cada intersección de un par de conjuntos. Pero al hacer esto se eliminan los elementos que están en los tres conjuntos una vez con demasiada frecuencia, por lo que necesitamos agregarlo de nuevo. En cuanto a cardinalidad de conjuntos, tenemos

\ begin {ecuación*} |A\ copa B\ copa C| = |A| + |B| + |C| - |A\ cap B| - |A\ cap C| - |B\ cap C| + |A\ cap B\ cap C|. \ end {ecuación*}

Ejemplo\(\PageIndex{1}\):

Tres niños, Alberto, Bernadette y Carlos, deciden compartir 11 galletas. Se preguntan de cuántas formas podrían dividir las cookies siempre que ninguna de ellas reciba más de 4 cookies (alguien que no reciba cookies es por alguna razón aceptable para estos niños).

Solución

Sin la restricción de “no más de 4”, la respuesta sería\({13 \choose 2}\text{,}\) usar 11 estrellas y 2 barras (separando a los tres niños). Ahora cuente el número de formas en que uno o más de los niños viole la condición, es decir, obtiene al menos 4 galletas.

\(A\)Sea el conjunto de resultados en los que Alberto obtiene más de 4 cookies. \(B\)Sea el conjunto de resultados en los que Bernadette obtiene más de 4 cookies. \(C\)Sea el conjunto de resultados en los que Carlos obtiene más de 4 cookies. Entonces estamos buscando (por el bien de la resta) el tamaño del conjunto\(A \cup B \cup C\text{.}\) Usando PIE, debemos encontrar los tamaños de\(|A|\text{,}\)\(|B|\text{,}\)\(|C|\text{,}\)\(|A\cap B|\) y así sucesivamente. Esto es lo que encontramos.

\(|A| = {8 \choose 2}\text{.}\)Primero dale a Alberto 5 galletas, luego distribuye las 6 restantes a los tres niños sin restricciones, usando 6 estrellas y 2 barras.
\(|B| = {8 \choose 2}\text{.}\)Al igual que arriba, solo ahora Bernadette obtiene 5 galletas al inicio.
\(|C| = {8 \choose 2}\text{.}\)Carlos obtiene 5 galletas primero.
\(|A \cap B| = {3 \choose 2}\text{.}\)Dale a Alberto y Bernadette 5 galletas cada una, dejando 1 (estrella) para distribuir a los tres niños (2 barras).
\(|A \cap C| = {3 \choose 2}\text{.}\)Alberto y Carlos obtienen 5 galletas primero.
\(|B \cap C| = {3 \choose 2}\text{.}\)Bernadette y Carlos obtienen 5 galletas primero.
\(|A \cap B \cap C| = 0\text{.}\)No es posible que los tres niños obtengan 4 o más galletas.

Combinando todos estos vemos

\ begin {ecuación*} |A\ copa B\ copa C| = {8\ elige 2} + {8\ elige 2} + {8\ elige 2} - {3\ elige 2} - {3\ elige 2} - {3\ elige 2} + 0 = 75. \ end {ecuación*}

Así la respuesta a la pregunta original es\({13 \choose 2} - 75 = 78 - 75 = 3\text{.}\) Esto tiene sentido ahora que la vemos. La única forma de asegurarse de que ningún niño obtenga más de 4 galletas es darle a dos niños 4 galletas y un niño 3; hay tres opciones para qué niño debería ser. Podríamos haber encontrado la respuesta mucho más rápido a través de esta observación, pero el objetivo del ejemplo es ilustrar que PIE funciona!

Para cuatro o más series, no escribimos una fórmula para PIE. En cambio, solo pensamos en el principio: sumar todos los elementos en conjuntos individuales, luego restar cosas que contaste dos veces (elementos en la intersección de un par de conjuntos), luego volver a sumar elementos que eliminaste con demasiada frecuencia (elementos en la intersección de grupos de tres conjuntos), luego sacamos de nuevo elementos que volviste a agregar con demasiada frecuencia (elementos en la intersección de grupos de cuatro conjuntos), luego volver a agregar, volver a agregar, etc. Esto sería muy difícil si no fuera por el hecho de que en estos problemas, todas las cardinalidades de los conjuntos individuales son iguales, al igual que todas las cardinalidades del intersecciones de dos conjuntos, y la de tres conjuntos, y así sucesivamente. Así podemos agrupar todos estos juntos y multiplicar por cuántas combinaciones diferentes de 1, 2, 3,... conjuntos hay.

Ejemplo\(\PageIndex{2}\)

¿De cuántas formas puedes distribuir 10 galletas a 4 niños para que ningún niño obtenga más de 2 galletas?

Solución

Hay\({13 \choose 3}\) formas de distribuir 10 galletas a 4 niños (usando 10 estrellas y 3 barras). Vamos a restar todos los resultados en los que un niño obtiene 3 o más galletas. ¿Cuántos resultados hay así? Podemos obligar al niño A a comer 3 o más galletas dándole 3 galletas antes de comenzar. Hacerlo reduce el problema a uno en el que tenemos 7 cookies para dar a 4 niños sin ninguna restricción. En ese caso, tenemos 7 estrellas (las 7 cookies restantes) y 3 barras (una menos que el número de niños) para que podamos distribuir las cookies de\({10 \choose 3}\) maneras. Por supuesto que podríamos elegir cualquiera de los 4 niños para dar demasiadas galletas, por lo que parecería que hay\({4 \choose 1}{10 \choose 3}\) formas de distribuir las galletas dando demasiadas a un niño. Pero de hecho, hemos sobrecontado.

Debemos deshacernos de los resultados en los que dos niños tienen demasiadas galletas. Hay\({4 \choose 2}\) formas de seleccionar 2 niños para dar galletas adicionales. Se necesitan 6 cookies para hacer esto, dejando solo 4 cookies. Así que tenemos 4 estrellas y todavía 3 barras. Por lo tanto, las 4 cookies restantes se pueden distribuir de\({7 \choose 3}\) maneras (para cada una de las\({4 \choose 2}\) opciones de las cuales 2 niños sobrealimentarse).

Pero ahora hemos quitado demasiado. Debemos volver a agregar en todas las formas para darle demasiadas galletas a tres niños. Esto utiliza 9 cookies, dejando solo 1 para distribuir a los 4 niños usando estrellas y barras, lo que se puede hacer de\({4 \choose 3}\) maneras. Debemos considerar este resultado para cada elección posible de qué tres niños sobrealimentamos, y hay\({4 \choose 3}\) formas de seleccionar ese conjunto de 3 niños.

A continuación restaríamos todas las formas de darle demasiadas galletas a cuatro niños, pero en este caso, ese número es 0.

Todos juntos conseguimos que la cantidad de formas de distribuir 10 cookies a 4 niños sin darle a ningún niño más de 2 cookies es:

\ begin {ecuación*} {13\ elige 3} -\ left [{4\ elige 1} {10\ elige 3} - {4\ elige 2} {7\ elige 3} + {4\ elige 3} {4\ elige 3}\ derecha]\ end {ecuación*}
que es

\ begin {ecuación*} 286 - [480 - 210 + 16] = 0. \ end {equation*}
Esto tiene sentido: NO hay forma de distribuir 10 galletas a 4 niños y asegurarse de que nadie obtenga más de 2. Es un poco sorprendente que

\ begin {ecuación*} {13\ elige 3} =\ left [{4\ elige 1} {10\ elige 3} - {4\ elige 2} {7\ elige 3} + {4\ elige 3} {4\ elige 3}\ derecha]\ end {ecuación*}

pero como funciona PIE, esta igualdad debe sostenerse.

Sólo para que no pienses que estos problemas siempre tienen soluciones más fáciles, considera el siguiente ejemplo.

Ejemplo\(\PageIndex{3}\)

Anteriormente (Ejemplo 1.5.3) contamos el número de soluciones a la ecuación

\ start {ecuación*} x_1 + x_2 + x_3 + x_4 + x_5 = 13\ final {ecuación*}

donde\(x_i \ge 0\) para cada\(x_i\text{.}\)

Cuántas de esas soluciones tienen\(0 \le x_i \le 3\) para cada\(x_i\text{?}\)

Solución

Debemos restar el número de soluciones en las que una o más de las variables tiene un valor mayor a 3. Tendremos que usar PIE porque contando el número de soluciones para las cuales cada una de las cinco variables por separado son mayores de 3 recuentos soluciones múltiples veces. Esto es lo que obtenemos:

• Soluciones totales:\({17 \choose 4}\text{.}\)
• Soluciones donde\(x_1 > 3\text{:}\)\({13 \choose 4}\text{.}\) Dar\(x_1\) 4 unidades primero, luego distribuir las 9 unidades restantes a las 5 variables.
• Soluciones donde\(x_1 > 3\) y\(x_2 > 3\text{:}\)\({9 \choose 4}\text{.}\) Después de dar 4 unidades a\(x_1\) y otras 4 a\(x_2\text{,}\) usted solo le quedan 5 unidades para distribuir.
• Soluciones donde\(x_1 > 3\text{,}\)\(x_2 > 3\) y\(x_3 > 3\text{:}\)\({5 \choose 4}\text{.}\)
• Soluciones donde\(x_1 > 3\text{,}\)\(x_2 > 3\text{,}\)\(x_3 > 3\text{,}\) y\(x_4 > 3\text{:}\) 0.

También tenemos que dar cuenta del hecho de que podríamos elegir cualquiera de las cinco variables en el lugar de\(x_1\) arriba (así habrá\({5 \choose 1}\) resultados como este), cualquier par de variables en el lugar de\(x_1\) y\(x_2\) (\({5 \choose 2}\)resultados) y así sucesivamente. Es por esto que se produce el doble conteo, por lo que necesitamos usar PIE. Todos juntos tenemos que la cantidad de soluciones con\(0 \le x_i \le 3\) es

\ begin {ecuación*} {17\ elige 4} -\ left [{5\ elige 1} {13\ elige 4} - {5\ elige 2} {9\ elige 4} + {5\ elige 3} {5\ elige 4}\ derecha] = 15. \ end {ecuación*}

Desordenamientos de conteo

¡Investiga!

Para tu broma senior, decides cambiar las placas de identificación en las puertas de tus 5 profesores favoritos. Para que ninguno de ellos se sienta excluido, quieres asegurarte de que todas las placas de identificación terminen en la puerta equivocada. ¿De cuántas maneras se puede lograr esto?

El uso avanzado de PIE tiene aplicaciones más allá de estrellas y barras. Un desajuste de\(n\) elementos\(\{1,2,3,\ldots, n\}\) es una permutación en la que no se fija ningún elemento. Por ejemplo, hay\(6\) permutaciones de los tres elementos\(\{1,2,3\}\text{:}\)

\ begin {ecuación*} 123 ~~ 132 ~~ 213 ~~ 231 ~~ 312 ~~ 321. \ end {ecuación*}

pero la mayoría de estos tienen uno o más elementos fijos:\(123\) tiene los tres elementos fijos ya que los tres elementos están en sus posiciones originales,\(132\) tiene el primer elemento fijo (1 está en su primera posición original), y así sucesivamente. De hecho, los únicos desajustes de tres elementos son

\ begin {ecuación*} 231\ texto {y} 312. \ end {ecuación*}

Si vamos hasta 4 elementos, hay 24 permutaciones (porque tenemos 4 opciones para el primer elemento, 3 opciones para el segundo, 2 opciones para el tercero dejando solo 1 opción para el último). ¿Cuántos de estos son descarrilamientos? Si enumeras todas las 24 permutaciones y eliminas aquellas que no son desórdenes, te quedarás con solo 9 desórdenes. Veamos cómo podemos obtener ese número usando PIE.

Ejemplo\(\PageIndex{4}\)

¿Cuántos descarrilamientos hay de 4 elementos?

Solución

Contamos todas las permutaciones, y restamos las que no son desórdenes. Hay\(4! = 24\) permutaciones de 4 elementos. Ahora para que una permutación no sea un desajuste, se debe fijar al menos uno de los 4 elementos. Hay\({4 \choose 1}\) opciones para qué elemento único arreglamos. Una vez arreglados, necesitamos encontrar una permutación de los otros tres elementos. Hay\(3!\) permutaciones en 3 elementos. Pero ahora hemos contado demasiados no descarrilamientos, por lo que debemos restar esas permutaciones que fijan dos elementos. Hay\({4 \choose 2}\) opciones para las que fijamos dos elementos, y luego para cada par,\(2!\) permutaciones de los elementos restantes. Pero esto resta demasiadas, así que vuelve a sumar permutaciones que fijan 3 elementos, todos\({4 \choose 3}1!\) ellos. Finalmente restar las\({4 \choose 4}0!\) permutaciones (recordar\(0! = 1\)) que fijan los cuatro elementos. Todos juntos conseguimos que el número de descarrilamientos de 4 elementos es:

\ begin {ecuación*} 4! -\ left [{4\ elige 1} 3! - {4\ elige 2} 2! + {4\ elige 3} 1! - {4\ elige 4} 0! \ derecha] = 24 - 15 = 9. \ end {ecuación*}

Por supuesto que podemos usar una fórmula similar para contar los desajustes de cualquier número de elementos. No obstante, cuantos más elementos tengamos, más tiempo se vuelve la fórmula. Aquí hay otro ejemplo:

Ejemplo\(\PageIndex{5}\)

Cinco señores asisten a una fiesta, dejando sus sombreros en la puerta. Al final de la fiesta, se apresuran a agarrar sombreros al salir. ¿De cuántas maneras diferentes podría suceder esto para que ninguno de los señores se vaya con su propio sombrero?

Solución

Estamos contando desórdenes en 5 elementos. Hay\(5!\) formas de que los caballeros agarren sombreros en cualquier orden, pero muchas de estas permutaciones harán que alguien obtenga su propio sombrero. Entonces restamos todas las formas en que uno o más de los hombres obtienen su propio sombrero. En otras palabras, restamos los no descarrilamientos. Hacerlo requiere PIE. Así la respuesta es:

\ begin {ecuación*} 5! -\ left [{5\ elige 1} 4! - {5\ elige 2} 3! + {5\ elige 3} 2! - {5\ elige 4} ¡1! + {5\ elige 5} 0! \ derecho]. \ end {ecuación*}

Funciones de conteo

¡Investiga!

• Considera todas las funciones\(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) ¿Cuántas funciones hay todas juntas? ¿Cuántos de esos son inyectables? Recuerde, una función es una inyección si cada entrada va a una salida diferente.
• Considerar todas las funciones\(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) ¿Cuántas de las inyecciones tienen la propiedad que\(f(x) \ne x\) para alguna\(x \in \{1,2,3,4,5\}\)? Tu amigo afirma que la respuesta es:\ begin {equation*} 5! -\ left [{5\ elige 1} 4! - {5\ elige 2} 3! + {5\ elige 3} 2! - {5\ elige 4} ¡1! + {5\ elige 5} 0! \ derecho]. \ end {equation*} Explica por qué esto es correcto.
• Recordemos que una sobreyección es una función para la cual cada elemento del codominio está en el rango. ¿Cuántas de las funciones\(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\) son suryectivas? ¡Usa PIE!

Hemos visto a lo largo de este capítulo que muchas preguntas de conteo pueden reformularse como preguntas sobre funciones de conteo con ciertas propiedades. Esto es razonable ya que muchas preguntas de conteo pueden considerarse como contando el número de formas de asignar elementos de un conjunto a elementos de otro.

Ejemplo\(\PageIndex{6}\)

Tú decides regalar tu colección de videojuegos para que mejor dediques tu tiempo a estudiar matemáticas avanzadas. De cuántas maneras puedes hacer esto, siempre y cuando:

1. ¿Quieres distribuir tus 3 juegos diferentes de PS4 entre 5 amigos, para que ningún amigo obtenga más de un juego?
2. ¿Quieres distribuir tus 8 juegos diferentes de 3DS entre 5 amigos?
3. ¿Quieres distribuir tus 8 juegos diferentes de SNES entre 5 amigos, para que cada amigo obtenga al menos un juego?

En cada caso, modelar la pregunta de conteo como una pregunta de conteo de función.

Solución

Debemos usar los tres juegos (llamarlos 1, 2, 3) como dominio y los 5 amigos (a, b, c, d, e) como codominio (de lo contrario la función no se definiría para todo el dominio cuando un amigo no obtuviera ningún juego). Entonces, ¿cuántas funciones hay con dominio\(\{1,2,3\}\) and codomain \(\{a,b,c,d,e\}\text{?}\) The answer to this is \(5^3=125\text{,}\) since we can assign any of 5 elements to be the image of 1, any of 5 elements to be the image of 2 and any of 5 elements to be the image of 3.

Pero esta no es la respuesta correcta a nuestro problema de conteo, porque una de estas funciones es\(f= \twoline{1\amp 2\amp 3}{a\amp a\amp a}\text{;}\) one friend can get more than one game. What we really need to do is count injective functions. This gives \(P(5,3) = 60\) functions, which is the answer to our counting question.

Nuevamente, necesitamos usar los 8 juegos como dominio y los 5 amigos como codominio. Estamos contando todas las funciones, así que el número de formas de distribuir los juegos es\(5^8\text{.}\)

Esta pregunta es más difícil. Usa los juegos como dominio y amigos como codominio (de lo contrario un elemento del dominio tendría más de una imagen, lo cual es imposible). Asegurarse de que cada amigo obtenga al menos un juego significa que cada elemento del codominio está en el rango. En otras palabras, estamos buscando funciones suryectivas. ¿Cómo se cuentan esos?

En el Ejemplo 1.1.5 vimos cómo contar todas las funciones (usando el principio multiplicativo) y en el Ejemplo 1.3.4 aprendimos a contar las funciones inyectoras (usando permutaciones). Las funciones suryectivas no se cuentan tan fácilmente (a menos que el tamaño del dominio sea menor que el codominio, en cuyo caso no las hay).

La idea es contar las funciones que no son suryectivas, y luego restarlas del número total de funciones. Esto funciona muy bien cuando el codominio tiene dos elementos en él:

Ejemplo\(\PageIndex{7}\)

¿Cuántas funciones\(f: \{1,2,3,4,5\} \to \{a,b\}\) son suryectivas?

Solución

Hay\(2^5\) functions all together, two choices for where to send each of the 5 elements of the domain. Now of these, the functions which are not surjective must exclude one or more elements of the codomain from the range. So first, consider functions for which \(a\) is not in the range. This can only happen one way: everything gets sent to \(b\text{.}\) Alternatively, we could exclude \(b\) from the range. Then everything gets sent to \(a\text{,}\) so there is only one function like this. These are the only ways in which a function could not be surjective (no function excludes both \(a\) and \(b\) from the range) so there are exactly \(2^5 - 2\) surjective functions.

Cuando hay tres elementos en el codominio, ahora hay tres opciones para que un solo elemento excluya del rango. Adicionalmente, podríamos elegir pares de dos elementos para excluir del rango, y debemos asegurarnos de que no los contemos en exceso. ¡Es hora de PIE!

Ejemplo\(\PageIndex{8}\)

¿Cuántas funciones\(f: \{1,2,3,4,5\} \to \{a,b,c\}\) son suryectivas?

Solución

Nuevamente comience con el número total de funciones:\(3^5\) (as each of the five elements of the domain can go to any of three elements of the codomain). Now we count the functions which are not surjective.

Comience excluyendo\(a\) from the range. Then we have two choices (\(b\) or \(c\)) for where to send each of the five elements of the domain. Thus there are \(2^5\) functions which exclude \(a\) from the range. Similarly, there are \(2^5\) functions which exclude \(b\text{,}\) and another \(2^5\) which exclude \(c\text{.}\) Now have we counted all functions which are not surjective? Yes, but in fact, we have counted some multiple times. For example, the function which sends everything to \(c\) was one of the \(2^5\) functions we counted when we excluded \(a\) from the range, and also one of the \(2^5\) functions we counted when we excluded \(b\) from the range. We must subtract out all the functions which specifically exclude two elements from the range. There is 1 function when we exclude \(a\) and \(b\) (everything goes to \(c\)), one function when we exclude \(a\) and \(c\text{,}\) and one function when we exclude \(b\) and \(c\text{.}\)

Estamos usando PIE: para contar las funciones que no son suryectivas, sumamos las funciones que excluyen\(a\text{,}\) \(b\text{,}\) and \(c\) separately, then subtracted the functions which exclude pairs of elements. We would then add back in the functions which exclude groups of three elements, except that there are no such functions. We find that the number of functions which are not surjective is

\ begin {ecuación*} 2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0. \ end {ecuación*}

Quizás una forma más descriptiva de escribir esto es

\ begin {ecuación*} {3\ elige 1} 2^5 - {3\ elige 2} 1^5 + {3\ elige 3} 0^5. \ end {ecuación*}

ya que cada una de las\(2^5\)'s was the result of choosing 1 of the 3 elements of the codomain to exclude from the range, each of the three \(1^5\)'s was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing \(1^5\) instead of 1 makes sense too: we have 1 choice of were to send each of the 5 elements of the domain.

Ahora por fin podemos contar el número de funciones suryectivas:

\ begin {ecuación*} 3^5 -\ left [{3\ choose 1} 2^5 - {3\ choose 2} 1^5\ right] = 150. \ end {ecuación*}

Puede que te preocupe que contar funciones suryectivas cuando el codominio es mayor que 3 elementos sería demasiado tedioso. Necesitamos usar PIE pero con más de 3 juegos la fórmula para PIE es muy larga. Sin embargo, hemos tenido suerte. Como vimos en el ejemplo anterior, el número de funciones que excluyen a un solo elemento del rango es el mismo sin importar qué elemento único se excluya. Del mismo modo, el número de funciones que excluyen un par de elementos será el mismo para cada par. Con codominios más grandes, veremos el mismo comportamiento con grupos de 3, 4 y más elementos excluidos. Entonces, en lugar de sumar/restar cada uno de estos, simplemente podemos sumarlos o restarlos todos a la vez, si sabes cuántos hay. Esto funciona igual que lo hizo para los otros tipos de preguntas de conteo en esta sección, solo que ahora el tamaño de las diversas combinaciones de conjuntos es un número elevado a una potencia, a diferencia de un coeficiente binomial o factorial. Esto es lo que sucede con\(4\) y\(5\) elementos en el codominio.

Ejemplo\(\PageIndex{9}\)

1. ¿Cuántas funciones\(f: \{1,2,3,4,5\} \to \{a,b,c,d\}\) son suryectivas?
2. ¿Cuántas funciones\(f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}\) son suryectivas?

Solución

Hay\(4^5\) functions all together; we will subtract the functions which are not surjective. We could exclude any one of the four elements of the codomain, and doing so will leave us with \(3^5\) functions for each excluded element. This counts too many so we subtract the functions which exclude two of the four elements of the codomain, each pair giving \(2^5\) functions. But this excludes too many, so we add back in the functions which exclude three of the four elements of the codomain, each triple giving \(1^5\) function. There are \({4 \choose 1}\) groups of functions excluding a single element, \({4 \choose 2}\) groups of functions excluding a pair of elements, and \({4 \choose 3}\) groups of functions excluding a triple of elements. This means that the number of functions which are not surjective is:

\ begin {ecuación*} {4\ elige 1} 3^5 - {4\ elige 2} 2^5 + {4\ elige 3} 1^5. \ end {ecuación*}

Ahora podemos decir que el número de funciones que son suryectivas es:

\ begin {ecuación*} 4^5 -\ left [{4\ choose 1} 3^5 - {4\ choose 2} 2^5 + {4\ choose 3} 1^5\ right]. \ end {ecuación*}

El número de funciones suryectivas es:

\ begin {ecuación*} 5^5 -\ left [{5\ elige 1} 4^5 - {5\ elige 2} 3^5 + {5\ elige 3} 2^5 - {5\ elige 4} 1^5\ derecha]. \ end {ecuación*}

Tomamos el número total de funciones\(5^5\) and subtracted all that were not surjective. There were \({5 \choose 1}\) ways to select a single element from the codomain to exclude from the range, and for each there were \(4^5\) functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are \({5 \choose 2}\) choices for the two elements to exclude, and for each pair, \(3^5\) functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: \({5 \choose 3}\) choices for which three to exclude, and then \(2^5\) functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the \({5 \choose 4}\) choices of 4 elements.

Si por casualidad calculas este número con precisión, obtendrás 120 sobrejecciones. Eso pasa a ser también el valor de\(5!\text{.}\) This might seem like an amazing coincidence until you realize that every surjective function \(f:X \to Y\) with \(\card{X} = \card{Y}\) finite must necessarily be a bijection. The number of bijections is always \(\card{X}!\) in this case. What we have here is a combinatorial proof of the following identity:

\ comenzar {ecuación*} n^n -\ izquierda [{n\ elige 1} (n-1) ^n - {n\ elige 2} (n-2) ^n +\ cdots + {n\ elige n-1} 1^n\ derecha] = n!. \ end {ecuación*}

Hemos visto que contar funciones suryectivas es otro buen ejemplo del uso avanzado del Principio de Inclusión/Exclusión. Además, contar funciones inyectoras resulta ser equivalente a permutaciones, y contar todas las funciones tiene una solución similar a aquellos problemas de conteo donde el orden importa pero se permiten repeticiones (como contar el número de palabras que puedes hacer a partir de un conjunto de letras dado).

Estos no son solo algunos ejemplos más de las técnicas que hemos desarrollado en este capítulo. Todo lo contrario: ¡todo lo que hemos aprendido en este capítulo son ejemplos de funciones de conteo!

Ejemplo\(\PageIndex{10}\)

¿Cuántas palabras de 5 letras puedes hacer usando las ocho letras\(a\) a través de\(h\text{?}\) ¿Cuántas no contienen letras repetidas?

Solución

A estas alturas no debería sorprendernos que haya\(8^5\) words, and \(P(8,5)\) words without repeated letters. The new piece here is that we are actually counting functions. For the first problem, we are counting all functions from \(\{1,2,\ldots, 5\}\) to \(\{a,b,\ldots, h\}\text{.}\) The numbers in the domain represent the position of the letter in the word, the codomain represents the letter that could be assigned to that position. If we ask for no repeated letters, we are asking for injective functions.

Si\(A\) and \(B\) are any sets with \(|A| = 5\) and \(|B| = 8\text{,}\) then the number of functions \(f: A \to B\) is \(8^5\) and the number of injections is \(P(8,5)\text{.}\) So if you can represent your counting problem as a function counting problem, most of the work is done.

Ejemplo\(\PageIndex{11}\)

¿Cuántos subconjuntos hay de\(\{1,2,\ldots, 9\}\text{?}\) ¿Cuántas cadenas de 9 bits hay (de cualquier peso)?

Solución

Vimos en la Sección 1.2 que la respuesta a ambas preguntas es\(2^9\text{,}\) as we can say yes or no (or 0 or 1) to each of the 9 elements in the set (positions in the bit-string). But \(2^9\) also looks like the answer you get from counting functions. In fact, if you count all functions \(f: A \to B\) with \(|A| = 9\) and \(|B| = 2\text{,}\) this is exactly what you get.

¡Esto tiene sentido! Let\(A = \{1,2,\ldots, 9\}\) and \(B = \{y, n\}\text{.}\) We are assigning each element of the set either a yes or a no. Or in the language of bit-strings, we would take the 9 positions in the bit string as our domain and the set \(\{0,1\}\) as the codomain.

Hasta el momento no hemos utilizado una función como modelo para los coeficientes binomiales (combinaciones). Piense por un momento en la relación entre combinaciones y permutaciones, digamos específicamente\({9 \choose 3}\) y\(P(9,3)\text{.}\) tenemos un modelo de función para\(P(9,3)\text{.}\) Este es el número de funciones inyectoras de un conjunto de tamaño 3 (digamos\(\{1,2,3\}\) a un conjunto de tamaño 9 (digamos\(\{1,2,\ldots, 9\}\)) ya que hay 9 opciones de dónde enviar el primer elemento del dominio, entonces sólo 8 opciones para el segundo, y 7 opciones para el tercero. Por ejemplo, la función podría verse así:

\ begin {ecuación*} f (1) = 5\ qquad f (2) = 8\ qquad f (3) = 4. \ end {ecuación*}

Esta es una función diferente de:

\ begin {ecuación*} f (1) = 4\ qquad f (2) = 5\ qquad f (3) = 8. \ end {ecuación*}

Ahora los\(P(9,3)\) cuenta como resultados diferentes correctamente, pero los\({9\choose 3}\) contará (entre otros) como un solo resultado. De hecho, en términos de funciones\({9 \choose 3}\) solo cuenta el número de diferentes rangos posibles de funciones inyectoras. Esto no debería ser una sorpresa ya que los coeficientes binomiales cuentan subconjuntos, y el rango es un posible subconjunto del codominio. ⁴ Una interpretación matemáticamente más sofisticada de las combinaciones es que estamos definiendo dos funciones inyectoras para que sean equivalentes si tienen el mismo rango, y luego contando el número de clases de equivalencia bajo esta noción de equivalencia.

Si bien es posible interpretar las combinaciones como funciones, quizás el mejor consejo es usar combinaciones (o estrellas y barras) cuando las funciones no son la forma correcta de interpretar la pregunta de conteo.