7.3: Uso de funciones de generación para contar cosas

Como cabría esperar de algo que ha surgido en nuestro estudio de la enumeración, generar funciones puede ser útil para resolver problemas de conteo. Ya hemos visto del Teorema Binomial, que el coeficiente de\(x^r\) in\((1 + x)^n\), es\(\binom{n}{r}\), así es la función generadora para los coeficientes binomiales\((1 + x)^n\). De hecho, el argumento que utilizamos para probar el Teorema Binomial explicó por qué esto funciona: si queremos el coeficiente de\(x^r\) in\((1 + x)^n\), debe ser el número de formas de elegir el\(x\)\(r\) de los\(n\) factores, mientras que elegir el\(1\) de los otros factores. Podemos usar razonamientos similares para resolver otras preguntas de conteo.

Ejemplo\(\PageIndex{1}\)

La tienda de abarrotes vende platos de papel en paquetes de\(1\)\(5\),\(20\),, o\(75\). ¿De cuántas maneras diferentes puede Jiping comprar un total de platos de\(95\) papel?

Solución

Modelamos esto con funciones generadoras. El exponente de\(x\) representará el número de platos de papel, y el coeficiente de\(x^n\) representará el número de formas en que puede comprar platos de\(n\) papel.

Comenzamos por considerar los platos de papel individuales que compra. Podría comprar\(0\), o\(1\), o cualquier otro número de estos, así que representamos esto por la función generadora.

\(1 + x + x^2 + x^3 + x^4 + . . . = \sum_{i=0}^{\infty} x^i = \dfrac{1}{(1-x)} \)

Hay exactamente una manera de elegir cualquier número particular de platos de papel individuales (estamos asumiendo que los platos son indistinguibles).

Ahora, también podría comprar cualquier cantidad de paquetes de platos de\(5\) papel, pero la diferencia es que cada paquete que compra contribuye\(5\) al exponente, ya que representa\(5\) platos. Representamos esto por la función generadora

\(1 + x^5 + x^{10} + x^{15} + . . . = \sum_{i=0}^{\infty} x^{5i} = \dfrac{1}{(1-x^5)} \)

donde\(i\) representa el número de paquetes que compra.

De igual manera, podría comprar cualquier cantidad de paquetes de platos de\(20\) papel, y cada paquete que compre contribuye\(20\) al exponente, ya que representa\(20\) platos. Representamos esto por la función generadora

\(1 + x^{20} + x^{40} + x^{60} + . . . = \sum_{i=0}^{\infty} x^{20i} = \dfrac{1}{(1-x^{20})} \)

donde\(i\) representa el número de paquetes que compra.

Por último, podría comprar cualquier cantidad de paquetes de platos de\(75\) papel, y cada paquete que compra contribuye\(75\) al exponente, ya que representa\(75\) platos. Representamos esto por la función generadora

\(1 + x^{75} + x^{150} + x^{225} + . . . = \sum_{i=0}^{\infty} x^{75i} = \dfrac{1}{(1-x^{75})} \)

donde\(i\) representa el número de paquetes que compra.

Obviamente, para esta pregunta en particular, Jiping en realidad no puede comprar\(2\) ni más de los paquetes de platos de\(75\) papel, ya que serían demasiados. También hay límites en el número de paquetes de otros tamaños que debe comprar ya que no quiere terminar con más que\(95\) placas. Entonces, para este problema, podemos suponer que la función generadora para el problema completo en realidad se ve así:

\((1 + x + x^2 + . . . + x^{95})(1 + x^5 + x^{10} + . . . + x^{95})(1 + x^{20} + x^{40} + x^{60} + x^{80})(1 + x^{75})\)

y estamos buscando el coeficiente de\(x^{95}\).

Podríamos multiplicar todo esto para obtener nuestra respuesta. Podríamos ser un poco más inteligentes, reconociendo que solo nos importa realmente el coeficiente de\(x^{95}\), y desglosar el problema en casos dependiendo de cuántos de los paquetes más grandes compre. Cabe señalar que la función generadora realmente no nos ha ahorrado ningún trabajo. Este enfoque implica decir: “Bueno, si toma el\(x^{75}\) del factor final, entonces sólo hay seis formas de contribuir al coeficiente de\(x^{95}\): podría elegir un factor y\(1\) s anterior\(x^{20}\) de ambos factores; o podría elegir entre los factores anteriores; o podría\(1\) elegir entre los tercer factor y cualquiera de\(1\),\(x^5\),\(x^{10}\)\(x^{15}\),,, o\(x^{20}\) del segundo factor, en cada caso, elegir el término del primer factor que lleve al exponente hasta\(95\).” Esto equivale exactamente a decir: “Bueno, si compra un paquete de\(75\) platos, entonces solo hay seis formas de comprar\(95\) platos en total: podría comprar un paquete de\(20\) platos y hacerse; o podría comprar\(0\),\(1\),\(2\)\(3\), o\(4\) paquetes de \(5\)placas, en cada caso, comprando tantas placas individuales como sean necesarias para llevar el total hasta”\(95\).

Entonces, ¿cuál es la ventaja del enfoque de función generadora? Viene en un par de formas. Primero, resuelve múltiples problemas a la vez: si realmente multiplicamos la función generadora anterior, podremos leer no solo cuántas formas hay de comprar\(95\) placas, sino también cuántas formas hay de comprar cada número de placas hasta\(95\). (Si no hubiéramos cortado los factores como lo hicimos, también podríamos calcular las respuestas para cualquier número de placas mayor que\(95\).) Entonces, al hacer un montón de multiplicación una vez (y es fácil alimentar un sistema de álgebra computacional si no quieres hacerlo a mano), podemos encontrar simultáneamente la respuesta a muchas preguntas estrechamente relacionadas.

La otra ventaja es que el enfoque de función generadora puede ayudarnos a resolver problemas que no vemos cómo resolver sin ella, como encontrar una fórmula explícita para el\(n^{\text{th}}\) término de una secuencia definida recursivamente.

Aquí hay un ejemplo que implica trabajar el coeficiente de un término en una función generadora de dos maneras diferentes.

Ejemplo\(\PageIndex{2}\)

Considera la función generadora\(\left(\dfrac{1}{(1 − x)^4}\right) = (1 + x + x^2 + x^3 + . . .)^4\). Como es habitual, queremos determinar el coeficiente de\(x^r\) en este producto.

Solución

Debemos elegir un poder\(x\) de entre cada uno de los cuatro factores, de tal manera que la suma de los poderes que elegimos debe ser\(n\). Esto es lo mismo que elegir un total de\(r\) ítems, cuando los ítems vienen en cuatro tipos distintos (recordar, por ejemplo, Ejemplo 5.1.2). Los tipos están representados por el factor entre el que se elige el término, y el exponente elegido de ese factor es el número de ítems elegidos de ese tipo.\(x\) Entonces sabemos que la cantidad de formas de hacer esto es\(\left( \binom{4}{r} \right)\)

Tenemos otra forma de resolver esto. Nuestra función generadora es\((1 − x)^{−4}\), y el Teorema del Binomio Generalizado nos dice que el coeficiente de\((−x)^r\) en esto es\(\binom{−4}{r}\), entonces el coeficiente de\(x^r\) es

\((−1)^r (−1)^r \binom{r+3}{r} = \left( \binom{4}{r} \right) \)

Usaremos el ejemplo anterior para resolver una pregunta de conteo, pero primero necesitamos una observación.

Proposición\(\PageIndex{1}\)

Para cualquier entero positivo\(k\),

\[1 + x + x^2 + · · · + x^k = \dfrac{1-x^{k+1}}{1-x} \]

Puedes demostrarlo por inducción en\(k\) (este es uno de los ejercicios a continuación), o multiplicando por\(1 − x\).

Ejemplo\(\PageIndex{3}\)

Trent está jugando un juego de dados, usando dados\(12\) de lados. ¿De cuántas maneras hay para que ruede un total de\(24\) en sus cuatro dados?

Contestar

Cada dado puede rodar cualquier número entre\(1\) y\(12\), y hay cuatro dados, por lo que la función de generación apropiada es

\((x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11} + x^{12})^4\)

Hacer rodar un\(i\) sobre uno de los dados corresponde a\(x^i\) elegir entre el factor correspondiente de esta función generadora. Estamos buscando el coeficiente de\(x^{24}\), esto nos dirá el número de formas de rodar un total de\(24\).

Resulta que manipulando la función generadora, podemos resolverlo un poco más fácilmente que multiplicando esto. Al tomar un factor común de\(x\) cada uno de los cuatro factores, nuestra función generadora puede ser reescrita como

\(x^4(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11})^4\)

y el coeficiente de\(x^{24}\) en este, será el mismo que el coeficiente de\(x^{20}\) en

\((1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11})^4\)

Usando la Proposición 7.3.1, vemos que esta expresión puede ser reescrita como

\( \left( \dfrac{1-x^{12}}{1-x} \right)^4 \)

Usando el Teorema Binomial y sustituyendo\(y = −x^{12}\), vemos que

\( \begin{equation} \begin{split} (1 − x^{12})^4&= \binom{4}{0} (-x^{12})^0 + \binom{4}{1} (-x^{12})^1 + \binom{4}{2} (-x^{12})^2 + \binom{4}{3} (-x^{12})^3 + \binom{4}{4} (-x^{12})^4 \\ &= 1 − 4x^{12} + 12x^{24} − 4x^{36} + x^{48} \\ \end{split} \end{equation} \)

La mayoría de estos términos pueden ser ignorados, ya que no contribuirán al coeficiente de\(x^{20}\). Recordemos que la función que nos interesa es producto de esto\((1 − x)^{−4}\), con, y solo hay dos formas de obtener un\(x^{20}\) término de este producto: tomando el término constante que acabamos de resolver, y multiplicándolo por el\(x^{20}\) término de\((1 − x)^{−4}\); o tomando el\(x^{12}\) término que acabamos de resolver, y multiplicándolo por el\(x^8\) término de\((1 − x)^{−4}\). En el ejemplo anterior, calculamos que en\((1 − x)^{−4}\), el coeficiente de\(x^{20}\) es\(\left( \binom{4}{20} \right)\), y el coeficiente de\(x^8\) es\(\left( \binom{4}{8} \right)\).

Así, el número de formas en que Trent puede lanzar un total de\(24\) en sus cuatro dados es el coeficiente de\(x^{24}\) en nuestra función generadora, que es

\(\left( \binom{4}{20} \right) - 4 \left( \binom{4}{8} \right) = 1771 - 660 = 1111 \)

Ejercicio\(\PageIndex{1}\)

1. Probar Proposición 7.3.1 por inducción sobre\(k\).
2. Encuentra el número de formas en que Trent puede rodar un total de\(16\) en sus cuatro dados.
3. Si los cuatro dados de Trent son dados de\(10\) lados en lugar\(12\) de lados, ¿de cuántas formas puede lanzar un total de\(24\)?
4. Si Trent tira cinco dados regulares (\(6\)lados), ¿de cuántas formas puede rodar un total de\(11\)? Cuál es la probabilidad de que rolle un total de\(11\).