8.2: Otra mirada a la distribución de manzanas o carpetas
- Page ID
- 118346
Un problema recurrente hasta ahora en este libro ha sido considerar problemas que preguntan sobre la distribución de objetos indistinguibles (digamos manzanas) a entidades distintas (digamos hijos). Empezamos en el Capítulo 2 preguntando de cuántas formas había de distribuir 40 manzanas a 5 niños para que cada niño tenga la garantía de obtener al menos una manzana y vio que la respuesta era\(C(39,4)\). Incluso vimos cómo restringir la situación para que uno de los niños fuera limitado y pudiera recibir como máximo 10 manzanas. En el Capítulo 7 aprendimos a extender las restricciones para que más de un niño tuviera restricciones sobre el número de manzanas permitidas al aprovechar el Principio de Inclusión-Exclusión. Antes de pasar a ver cómo generar funciones puede permitirnos ser aún más creativos con nuestras restricciones, tomemos un momento para ver cómo generar funciones nos permitiría resolver el problema más básico que tenemos entre manos.
Ya sabemos que la cantidad de formas de distribuir\(n\) manzanas a 5 niños para que cada niño obtenga al menos una manzana es\(C(n−1,4)\), pero será instructivo ver cómo podemos derivar este resultado usando funciones generadoras. Empecemos con un problema aún más simple: ¿cuántas formas hay de distribuir n manzanas a un niño para que cada niño reciba al menos una manzana? Bueno, esto no es demasiado difícil, solo hay una manera de hacerlo: ¡dale todas las manzanas al chico afortunado! Así la secuencia que enumera el número de formas de hacerlo es\(\{a_n:n \geq 1\}\) con\(a_n=1\) para todos\(n \geq 1\). Entonces la función generadora para esta secuencia es
\(x+x^2+x^3+ \cdot \cdot \cdot = x(1+x+x^2+x^3+ \cdot \cdot \cdot) = \dfrac{x}{1-x}\)
¿Cómo podemos llegar de este hecho a la cuestión de cinco hijos? Observe lo que sucede cuando multiplicamos
\((x+x^2+\cdot \cdot \cdot)(x+x^2+ \cdot \cdot \cdot)(x+x^2+ \cdot \cdot \cdot)(x+x^2+\cdot \cdot \cdot)(x+x^2+\cdot \cdot \cdot)\).
Para ver lo que representa este producto, primero considera de cuántas maneras podemos obtener una\(x^6\)? Podríamos usar el\(x^2\) del primer factor y\(x\) de cada uno de los otros cuatro, o\(x^2\) del segundo factor y\(x\) de cada uno de los otros cuatro, etc., es decir, que el coeficiente on\(x^6\) es\(5=C(5,4)\). De manera más general, ¿cuál es el coeficiente\(x^n\) en el producto? En la expansión, obtenemos una\(x^n\) para cada producto de la forma\(x^{k_1}x^{k_2}x^{k_3}x^{k_4}x^{k_5}\) donde\(k_1+k_2+k_3+k_4+k_5=n\). Volviendo a la pregunta general aquí, realmente estamos tratando de distribuir\(n\) manzanas a 5 niños, y ya que\(k_i>0\) para\(i=1,2,…,5\), también tenemos la garantía de que cada niño recibe al menos una manzana, por lo que el producto de la función generadora para un niño da la función generadora para cinco hijos.
Vamos a fingir por un minuto que no sabíamos que los coeficientes debían ser\(C(n−1,4)\). ¿Cómo podríamos averiguar los coeficientes solo a partir de la función generadora? La función generadora que nos interesa es\(x^5/(1−x)^5\), que deberías poder ver muy rápidamente satisface
\(\dfrac{x^5}{(1-x)^5} = \dfrac{x^5}{4!} \dfrac{d^4}{dx^4}(\dfrac{1}{1-x}) = \dfrac{x^5}{4!} \displaystyle \sum_{n=0}^{\infty} n(n-1)(n-2)(n-3)x^{n-4}\)
\(= \displaystyle \sum_{n=0}^{\infty} \dfrac{n(n-1)(n-2)(n-3)}{4!} x^{n+1} = \sum_{n=0}^{\infty} \dbinom{n}{4} x^{n+1}\)
El coeficiente encendido\(x^n\) en esta serie\(C(n−1,4)\), tal como esperábamos.
Podríamos volver a visitar un ejemplo del Capítulo 7 para ver que si quisiéramos limitar a un niño a recibir como máximo 4 manzanas, usaríamos\((x+x^2+x^3+x^4)\) como su función generadora en lugar de\(x/(1−x)\), sino más bien que belabor que aquí, probemos algo un poco más exótico.
Una tienda de abarrotes está preparando cestas de frutas navideñas para la venta. Cada canasta de frutas tendrá 20 piezas de fruta, elegidas entre manzanas, peras, naranjas y pomelo. ¿De cuántas maneras diferentes se puede preparar una canasta de este tipo si debe haber al menos una manzana en una canasta, una canasta no puede contener más de tres peras, y el número de naranjas debe ser un múltiplo de cuatro?
- Solución
-
Para llegar al número de canastas que constan de 20 piezas de fruta, resolvamos el problema más general donde cada canasta tiene\(n\) trozos de fruta. Nuestro método es sencillo: encontrar la función generadora de cómo hacer esto con cada tipo de fruta individualmente y luego multiplicarlas. Al igual que en el ejemplo anterior, el producto contendrá el término\(x^n\) para cada forma de armar una canasta de\(n\) piezas de fruta sujeta a nuestras restricciones. La función generadora de manzana es\(x/(1−x)\), ya que solo queremos potencias positivas de\(x\) (correspondientes a asegurar al menos una manzana). La función generadora para las peras es\((1+x+x^2+x^3)\), ya que solo podemos tener cero, una, dos o tres peras en canasta. Para las naranjas tenemos\(1/(1−x^4)=1+x^4+x^8+ \cdot \cdot \cdot \), y el pomelo sin restricciones nos dan un factor de\(1/(1−x)\). Multiplicando, tenemos
\(\dfrac{x}{1-x}(1+x+x^2+x^3) \dfrac{1}{1-x^4} \dfrac{1}{1-x} = \dfrac{x}{(1-x)^2(1-x^4)}(1+x+x^2+x^3)\)
Ahora queremos hacer uso del hecho de que\((1+x+x^2+x^3)=(1−x^4)/(1−x)\) (por (8.1.1)) para ver que nuestra función generadora es
\(\dfrac{x}{(1-x)^3} = \dfrac{x}{2} \displaystyle \sum_{n=0}^{\infty} n(n-1)x^{n-2} = \sum_{n=0}^{\infty} \dfrac{n(n-1)}{2}x^{n-1}\)
\(= \displaystyle \sum_{n=0}^{\infty} \dbinom{n}{2}x^{n-1} = \sum_{n=0}^{\infty} \dbinom{n+1}{2}x^n\).
Así, existen\(C(n+1,2)\) posibles canastas de frutas que contienen\(n\) trozos de fruta, es decir, que la respuesta a la pregunta que originalmente hicimos es\(C(21,2)=210\).
La forma compacta de la solución al Ejemplo 8.5 sugiere que quizás haya una manera de llegar a esta respuesta sin el uso de funciones generadoras. Pensar en tal enfoque sería una buena manera de solidificar su comprensión de una variedad de los temas enumerativos que ya hemos cubierto.
Encuentra el número de soluciones enteras a la ecuación
\(x_1+x_2+x_3=n\)
(\(n \geq 0\)un entero) con\(x_1 \geq 0\) par,\(x_2 \geq 0\), y\(0 \leq x_3 \leq 2\).
- Solución
-
Nuevamente, queremos mirar la función generadora que tendríamos si cada variable existiera individualmente y tomar su producto. Porque\(x_1\), obtenemos un factor de\(1/(1−x^2)\); para\(x_2\), tenemos\(1/(1−x)\); y para\(x_3\) nuestro factor es\((1+x+x^2)\). Por lo tanto, la función generadora para el número de soluciones a la ecuación anterior es
\(\dfrac{1+x+x^2}{(1-x)(1-x^2)} = \dfrac{1+x+x^2}{(1+x)(1-x)^2}\).
En el cálculo, cuando quisiéramos integrar una función racional de esta forma, utilizaríamos el método de fracciones parciales para escribirla como una suma de funciones racionales “más simples” cuyas antiderivadas reconocimos. Aquí, nuestra técnica es la misma, ya que podemos reconocer fácilmente la serie formal de poder para muchas funciones racionales. Nuestro objetivo es escribir
\(\dfrac{1+x+x^2}{(1+x)(1-x)^2} = \dfrac{A}{1+x} + \dfrac{B}{1-x} + \dfrac{C}{(1-x)^2}\)
para constantes apropiadas,\(A, B\), y\(C\). Para encontrar las constantes, limpiamos los denominadores, dando
\(1+x+x^2 = A(1-x)^2 + B(1-x^2) + C(1+x)\).
Equiparando coeficientes en términos de igual grado, tenemos:
\(1=A+B+C\)
\(1=-2A+C\)
\(1=A-B\)
Resolviendo el sistema, encontramos\(A=1/4\),\(B=−3/4\), y\(C=3/2\). Por lo tanto, nuestra función generadora es
\(\dfrac{1}{4} \dfrac{1}{1+x} - \dfrac{3}{4} \dfrac{1}{1-x} + \dfrac{3}{2} \dfrac{1}{(1-x)^2}\)
\(=\dfrac{1}{4} \displaystyle \sum_{n=0}^{\infty} (-1)^n x^n - \dfrac{3}{4} \sum_{n=0}^{\infty} x^n + \dfrac{3}{2} \sum_{n=0}^{\infty} nx^{n-1}\)
La solución a nuestra pregunta es así el coeficiente sobre xn en la función generadora anterior, que es
\(\dfrac{(-1)^n}{4} - \dfrac{3}{4} + \dfrac{3(n+1)}{2}\),
¡una respuesta sorprendente que no sería muy fácil de encontrar a través de otros métodos!
La invocación de fracciones parciales en el Ejemplo 8.6 es poderosa, pero resolver el sistema necesario de ecuaciones y luego esperar que las series de poder formales resultantes tengan expansiones que reconocemos de inmediato puede ser un desafío. Si el Ejemplo 8.6 no hubiera preguntado sobre el caso general con n en el lado derecho de la ecuación sino que hubiera preguntado específicamente sobre, n=30, tal vez se esté preguntando si sería más rápido escribir algún código Python para generar todas las soluciones o más interesantes para acurrucarse e idear algunas estrategia inteligente para contarlos. Afortunadamente, la tecnología nos puede ayudar a la hora de trabajar con funciones de generación. En SameMath, podemos usar el método series () para obtener la expansión de la serie de potencia de una función dada. Los dos argumentos a la serie son la variable y el grado de los términos que se quiere truncar. En la celda de abajo, pedimos a SaeMath que expanda la función generadora del Ejemplo 8.6 dándonos todos los términos de grado como máximo 30 y luego colapsando el resto de la serie en su forma de notación Big-OH, que descartamos almacenando la salida de series () en un polinomio f (x).
\\ Código SagoMath
Si todo lo que realmente queremos es el coeficiente en un término específico, podemos usar el método list () para convertir el poliomial en una lista de sus coeficientes y luego indexar a esa lista usando la sintaxis estándar de SameMath o Python:
\\ Código
Veamos que la respuesta concuerda con lo que nos da nuestra fórmula en la solución al Ejemplo 8.6 para\(n=30\):
\\ Código
Eso es un alivio, y mientras solo necesitemos un solo coeficiente, ahora estamos en buena forma. Pero, ¿y si realmente necesitamos una fórmula para el coeficiente encendido\(x^n\) en general? Veamos cómo podemos usar SaeMath para ayudarnos con algunos de los otros pasos del Ejemplo 8.6. Lo primero que vamos a querer es el método partial_fraction ():
\\ Código
Si no te gusta la forma en que se ve, la función pretty_print () puede hacer que sea más fácil de leer:
\\ Código
Hasta la ubicación de un signo menos, esto es lo que conseguimos a mano, ¡pero lo conseguimos mucho más rápido! A partir de esta etapa, con frecuencia es posible utilizar nuestro conocimiento de ciertas series de potencias fundamentales que aparecen al hacer la expansión de fracciones parciales para llegar a la forma general del coeficiente en un término arbitrario de la serie de potencias. Para facilitar esto, cerramos esta sección con un ejemplo que ilustra cómo podemos usar soluciones a problemas de conteo que ya hemos estudiado con el fin de averiguar los coeficientes en la generación de funciones.
Dejar\(n\) ser un entero positivo. Cuál es el coeficiente encendido\(x^k\) en la función generadora
\(\dfrac{1}{(1-x)^n}\)?
- Solución
-
Ya nos encontramos con el caso n=5 en medio de trabajar en el Ejemplo 8.4, pero ahí apelamos al cálculo. Echemos un vistazo a esto desde la perspectiva de solo contar. La función generadora\(1/(1−x)=1+x+x^2+ \cdot \cdot \cdot \) codifica la secuencia para el número de formas de distribuir\(n\) manzanas a un hijo. Sólo hay una manera de hacer esa tarea: darle al chico afortunado todas las manzanas. Multiplicar juntos un montón de copias de\(1/(1−x)\) entonces sirve para incrementar el número de niños a los que se les están distribuyendo las manzanas, y dado que cada serie de poder que se multiplica comienza con 1, estamos en la situación en la que el número de manzanas que recibe cada niño debe ser no negativo . Por lo tanto, se trata de un problema de la Sección 2.5. Tenemos\(n\) hijos y el coeficiente encendido\(x^k\) es el número de formas de distribuirles\(k\) manzanas. Esto requiere de manzanas\(n\) artificiales, por lo que distribuimos\(k+n\) las manzanas, las cuales determinan\(k+n−1\) brechas y debemos elegir\(n−1\) de ellas como las ubicaciones para los divisores. Por lo tanto, podemos concluir que
\(\dfrac{1}{(1-x)^n} = \displaystyle \sum_{k=0}^{\infty} \dbinom{k+n-1}{n-1}x^k = \sum_{k=0}^{\infty} \dbinom{k+n-1}{n}x^k\).
Es posible llegar a esta conclusión usando técnicas de cálculo, pero hay muchos factoriales y −1s para monitorear, ¡así que este enfoque combinatorio puede ser menos propenso a errores!