7.3: Enumerar las suryecciones
- Page ID
- 118506
Como nuestro primer ejemplo del poder de inclusión-exclusión, considera la siguiente situación: Un abuelo tiene 15 boletos de lotería distintos y quiere distribuirlos a sus cuatro nietos para que cada niño obtenga al menos un boleto. ¿De cuántas maneras puede hacer tal distribución? Al principio, esto se parece mucho al problema de enumerar enteros soluciones de ecuaciones, ¡excepto aquí los boletos de lotería no son idénticos! Un boleto que lleve los números 1, 3, 10, 23, 47 y 50 casi seguramente no pagará la misma cantidad que uno con los números ,2, 7, 10, 30, 31 y 48, así que quién obtiene qué boleto realmente marca la diferencia. Ojalá ya hayas reconocido que el hecho de que estemos tratando con boletos de lotería y nietos no es tan importante aquí. Más bien, lo importante es que queremos distribuir objetos distinguibles a entidades distintas, lo que requiere contar funciones de un conjunto (boletos de lotería) a otro (nietos). En nuestro ejemplo, no queremos simplemente el número total de funciones, sino que queremos el número de surjecciones, para que podamos asegurarnos de que cada nieto obtenga un boleto.
Para los enteros positivos\(n\) y\(m\), vamos a\(S(n,m)\) denotar el número de sobrejecciones de\([n]\) a\([m]\). Tenga en cuenta que\(S(n,m)=0\) cuando\(n<m\). En esta sección, aplicamos la fórmula Inclusión-Exclusión para determinar una fórmula para\(S(n,m)\). Comenzamos configurando\(X\) para que sea el conjunto de todas las funciones desde\([n]\) hasta\([m]\). Entonces para todos\(f \in X\) y cada uno\(i=1,2,…,m\), decimos que\(f\) satisface la propiedad\(P_i\) si no\(i\) está en el rango de\(f\).
Para cada subconjunto\(S \subseteq [m]\), \(N(S)\)depende sólo de\(|S|\). De hecho, si\(|S|=k\), entonces
\(N(S) = (m-k)^n\).
- Prueba
-
Vamos\(|S|=k\). Entonces una función que\(f\) satisface la propiedad\(P_i\) para cada uno\(i \in S\) es una cadena de longitud\(n\) de un alfabeto que consiste en\(m−k\) letras. Esto demuestra que
\(N(S) = (m-k)^n\).
Ahora el siguiente resultado se desprende inmediatamente de este lema aplicando el Principio de Inclusión-Exclusión, ya que existen\(C(m,k)\)\(k\) -subconjuntos de elementos de\([m]\).
El número\(S(n,m)\) de suryecciones de\([n]\) a\([m]\) viene dado por:
\(S(n,m) = \displaystyle \sum_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n\).
Por ejemplo,
\(S(5,3) = \dbinom{3}{0}(3-0)^5 - \dbinom{3}{1}(3-1)^5 + \dbinom{3}{2}(3-2)^5 - \dbinom{3}{3}(3-3)^5\)
\(=243 - 96 + 3 - 0\)
\(=150\).
Volviendo a nuestro problema de distribución de boletos de lotería al inicio de la sección, vemos que hay\(S(15,4)=1016542800\) formas para que el abuelo distribuya sus 15 boletos de lotería para que cada uno de los 4 nietos reciba al menos un boleto.