8.8: Ejercicios

Los sistemas informáticos de álgebra pueden ser herramientas poderosas para trabajar con funciones generadoras. Sin embargo, a menos que un ejercicio sugiera específicamente que use un sistema de álgebra por computadora, le recomendamos encarecidamente que resuelva el problema a mano. Esto te ayudará a desarrollar una mejor comprensión de cómo se pueden usar las funciones generadoras. Podría considerar editar el contenido de las SAGEMathCells en la Sección 8.2 para ayudar a resolver problemas aquí donde se sugiere un sistema de álgebra por computadora, y en algunos casos, hemos incluido un SAGEMathCell dentro del ejercicio para que lo use.

Para todos los ejercicios de esta sección, “función generadora” debe tomarse como “función generadora ordinaria”. Las funciones generadoras exponenciales solo son necesarias en ejercicios que las mencionan específicamente.

1. Para cada secuencia finita a continuación, dar su función generadora.

a. 1, 4, 6, 4, 1 b. 1,1,1,1,0,0,1

c. 0,0,0,1,2,3,4,5 d. 1,1,1,1,1,1,1

e. 3,0,0,1, -4,7 f. 0,0,0,1,2, -3,0,1

2. Por cada secuencia infinita sugerida a continuación, dar su función generadora en forma cerrada, es decir, no como una suma infinita. (Utilice la elección de forma más obvia para el término general de cada secuencia.)

a. 0,1,1,1,1,... b. 1,0,0,1,0,0,1,0,0,1,0,0,1,...

c. 1,2,4,8,16,32 d. 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,...

e. 1, -1,1, -1,1, -1,1, -1,1, -1,... f.\(2^8, 2^7 \dbinom{8}{1}, 2^6 \dbinom{8}{2}, ..., \dbinom{8}{8},0,0,0,...\)

g. 1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,... h. 0,0,0,1,2,3,4,5,6,...

i. 3,2,4,1,1,1,1,1,1,... j. 0,2,0,0,2,0,0,2,0,0,0,0,2,0,0,2,...

k. 6,0, -6,0,6,0, -6,0,6,... l.\(1,3,6,10,15,..., \dbinom{n+2}{2},...\)

3. Para cada función generadora a continuación, dar una forma cerrada para el\(n^{th}\) término de su secuencia asociada.

a.\((1+x)^{10}\)

b.\(\dfrac{1}{1-x^4}\)

c.\(\dfrac{x^3}{1-x^4}\)

d.\(\dfrac{1-x^4}{1-x}\)

e.\(\dfrac{1+x^2-x^4}{1-x}\)

f.\(\dfrac{1}{1-4x}\)

g.\(\dfrac{1}{1+4x}\)

h.\(\dfrac{x^5}{(1-x)^4}\)

i.\(\dfrac{x^2+x+1}{1-x^7}\)

j.\(3x^4+7x^3-x^2+10+ \dfrac{1}{1-x^3}\)

4. Encuentra el coeficiente on\(x^{10}\) en cada una de las funciones generadoras a continuación.

a.\((x^3+x^5+x^6)(x^4+x^5+x^7)(1+x^5+x^{10}+x^{15}+ \cdot \cdot \cdot)\)

b.\((1+x^3)(x^3+x^4+x^5+ \cdot \cdot \cdot)(x^4+x^5+x^6+x^7+x^8+ \cdot \cdot \cdot)\)

c.\((1+x)^{12}\)

d.\(\dfrac{x^5}{1-3x^5}\)

e.\(\dfrac{1}{(1-x)^3}\)

f.\(\dfrac{1}{1-5x^4}\)

g.\(\dfrac{x}{1-2x^3}\)

h.\(\dfrac{1-x^{14}}{1-x}\)

5. Encuentre la función generadora de la cantidad de formas de crear un grupo de n globos seleccionados entre globos blancos, dorados y azules para que el grupo contenga al menos un globo blanco, al menos un globo dorado y como máximo dos globos azules. ¿Cuántas formas hay de crear un montón de 10 globos sujetos a estos requisitos?

6. Un coordinador de voluntarios tiene 30 galletas idénticas con chispas de chocolate para distribuir a seis voluntarios. Utilizar una función generadora (y sistema de álgebra informática) para determinar el número de formas en que puede distribuir las cookies para que cada voluntario reciba al menos dos cookies y no más de siete cookies.

//Código

7. Considerar la desigualdad

\(x_1+x_2+x_3+x_4 \leq n\)

donde\(x_1,x_2,x_3,x_4,n \geq 0\) están todos los enteros. Supongamos también que\(x_2 \geq 2\),\(x_3\) es un múltiplo de 4, y\(0 \leq x_4 \leq 3\). \(c_n\)Sea el número de soluciones de la desigualdad sujeta a estas restricciones. Encuentra la función generadora para la secuencia {\(c_n:n \geq 0\)} y úsala para encontrar una fórmula cerrada para\(c_n\).

8. Encuentra la función generadora de la cantidad de formas de distribuir papel rascar en blanco a Alice, Bob, Carlos y Dave para que Alice obtenga al menos dos hojas, Bob obtenga como máximo tres hojas, el número de hojas que recibe Carlos es un múltiplo de tres, y Dave obtiene al menos una hoja pero no más de seis hojas de papel rascar. Sin encontrar la expansión de la serie de potencia para esta función generadora (¡o usar un sistema de álgebra por computadora!) , determinar los coeficientes sobre\(x^2\) y\(x^3\) en esta función generadora.

9. ¿Cuál es la función generadora del número de formas de seleccionar un grupo de\(n\) alumnos de una clase de\(p\) alumnos?

10. Mediante funciones generadoras, encuentra una fórmula para el número de diferentes tipos de canastas de frutas que contengan\(n\) trozos de fruta elegidos entre granadas, plátanos, manzanas, naranjas, peras e higos que se pueden elaborar sujetos a las siguientes restricciones:

• hay 0 o 2 granadas
• hay al menos 1 plátano
• el número de higos es un múltiplo de 5
• hay como máximo 4 peras
• no hay restricciones en el número de manzanas o naranjas.

¿Cuántas formas hay de formar una canasta de frutas con\(n=25\) trozos de fruta?

11. Usando funciones de generación, encuentre la cantidad de formas de hacer cambios para un billete de 100 dólares usando solo monedas de dólar y billetes de $1, $2 y $5.

//Código

Pista

Encuentra la expansión de fracciones parciales para tu función generadora. Ten cuidado aquí, ya que quieres una expansión de fracción parcial en la que todos los coeficientes para tus polinomios denominador tengan coeficientes enteros. El método partial_fraction () en SageMath debería ser útil aquí, y pretty_print hará que sea más fácil de leer. Una vez que tenga la expansión de fracciones parciales correcta, puede resultarle útil la siguiente identidad

\(\dfrac{p(x)}{1+x+x^2+ \cdot \cdot \cdot + x^k} = \dfrac{p(x)(1-x)}{1-x^{k+1}}\),

donde\(p(x)\) será un polinomio en esta instancia.

12. Una empresaria viaja por Bélgica y quiere comprarse chocolates para ella, su esposo y sus dos hijas. Una tienda cuenta con trufas de chocolate negro (10 €/caja), trufas de chocolate con leche (8 €/caja), chocolates rellenos de turrón (5 €/caja), barras de chocolate con leche (7 €/barra) y barras de chocolate 75% cacao (11 €/barra). Su compra está sujeta a lo siguiente:

• Solo a las hijas les gustan las trufas de chocolate negro, y su compra debe asegurar que cada hija obtenga el mismo número de cajas de ellas (si obtienen alguna).
• Se deben adquirir al menos dos cajas de trufas de chocolate con leche.
• Si compra alguna caja de chocolates rellenos de turrón, entonces compra exactamente lo suficiente para que cada miembro de la familia obtenga precisamente una caja de ellos.
• Como máximo se pueden comprar tres barras de chocolate con leche.
• No hay restricciones en el número de barras de chocolate 75% cacao.

\(s_n\)Sea el número de formas en que la empresaria puede gastar exactamente €\(n\) (¡no comprar\(n\) artículos!) en esta chocolatería. Encuentra la función generadora para la secuencia\(\{s_n:n \geq 0\}\). ¿De cuántas maneras puede gastar exactamente 100€ en la chocolatería? (Un sistema de álgebra computacional será útil para encontrar coeficientes.)

//Código

13. Se están preparando bolsas de dulces para distribuir a los niños en una escuela. Los tipos de dulces disponibles son bocados de chocolate, tazas de mantequilla de maní, caramelos de menta y masticables de frutas. Cada bolsa debe contener al menos dos bocados de chocolate, un número par de tazas de mantequilla de maní y como máximo seis caramelos de menta. Los masticables de frutas están disponibles en cuatro sabores diferentes: limón, naranja, fresa y cereza. Una bolsa de dulces puede contener como máximo dos masticables de frutas, que pueden ser del mismo sabor o de diferentes sabores. Más allá del número de piezas de cada tipo de caramelo incluido, las bolsas de dulces se distinguen por usar los sabores de los masticables de frutas incluidos, no solo el número. Por ejemplo, una bolsa que contiene dos masticables de fruta naranja es diferente de una bolsa que contiene un masticable de cereza y un masticable de fruta de fresa, incluso si el número de piezas de cada otro tipo de caramelo es el mismo.

a. dejar\(b_n\) ser el número de diferentes bolsas de dulces con\(n\) trozos de caramelo que se pueden formar sujeto a estas restricciones. Encuentra la función generadora para la secuencia\(\{b_n:n \geq 0\}\).

b. Supongamos que la escuela tiene 400 alumnos y a los profesores les gustaría asegurarse de que cada alumno reciba una bolsa de dulces diferente. No obstante, saben que habrá peleas si las bolsas no contienen todas la misma cantidad de caramelos. ¿Cuál es el menor número de piezas de dulces que pueden incluir en las bolsas que asegura que cada estudiante obtenga una bolsa diferente de dulces que contenga el mismo número de piezas de caramelo?

14. Conformar un problema combinatorio (similar a los que se encuentran en este capítulo) que lleve a la función generadora

\(\dfrac{(1+x^2+x^4)x^2}{(1-x)^3(1-x^3)(1-x^{10})}\).

15. Las cabinas de peaje en Illinois aceptan todas las monedas estadounidenses, incluidos los centavos. Carlos tiene una oferta muy grande de centavos, monedas de cinco centavos, monedas de diez centavos y cuartos en su auto mientras conduce en una autopista de peaje. Se encuentra con un peaje por $0.95 y se pregunta cuántas formas diferentes podría usar su suministro de monedas para pagar el peaje sin que le devuelvan el cambio. (Un sistema de álgebra por computadora es probablemente la mejor manera de obtener el coeficiente requerido una vez que se tiene una función generadora, ya que no se le pide el coeficiente encendido\(x^n\).)

a. utilizar una función generadora y un sistema de álgebra computacional para determinar el número de formas en que Carlos podría pagar su peaje de $0.95 al colocar las monedas juntas en la papelera de peaje. (Supongamos que las monedas de la misma denominación no pueden distinguirse entre sí.)

b. Supongamos que en lugar de tener un contenedor en el que los automovilistas dejan caer las monedas para pagar su peaje, las monedas deben insertarse una por una en una ranura para monedas. En este escenario, Carlos se pregunta cuántas formas podría pagar el peaje de $0.95 cuando importa el pedido en que se insertan las monedas. Por ejemplo, en la parte anterior, el uso de tres cuartos y dos dimes se contabilizaría sólo una vez. Sin embargo, cuando las monedas deben insertarse individualmente en una ranura, hay\(10=C(5,2)\) formas de insertar esta combinación. Utilice una función generadora y un sistema de álgebra computacional para determinar el número de formas en que Carlos podría pagar el peaje de $0.95 al considerar el orden en que se insertan las monedas.

//Código

Pista

Para la parte b, realmente quieres una función generadora ordinaria y no una función generadora exponencial, a pesar de que el orden importa. Una vez que creas que tienes una función generadora que funciona, podrías verificar los coeficientes a\(x^5,…,x^{10}\) mano para asegurarte de que estás en el camino correcto.

16. Listar las particiones de 9. Escribe una D junto a cada partición en partes distintas y una O junto a cada partición en partes impares.

17. Utilice funciones de generación para encontrar el número de formas de dividir 10 en partes impares.

18. ¿Cuál es el entero más pequeño que se puede particionar de al menos 1000 formas? ¿De cuántas formas se puede particionar? ¿Cuántos de ellos están en partes distintas? (Un sistema de álgebra por computadora será útil para este ejercicio).

19. ¿Cuál es la función generadora para el número de particiones de un entero en partes pares?

20. Encuentra la función generadora exponencial (en forma cerrada, no como una suma infinita) para cada secuencia infinita\(\{a_n:n \geq 0\}\) cuyo término general se da a continuación.

a.\(a_n = 5^n\)

b.\(a_n = (-1)^n2^n\)

c.\(a_n = 3^{n+2}\)

d.\(a_n = n!\)

e.\(a_n = n\)

f.\(a_n = 1/(n+1)\)

21. Para cada función generadora exponencial a continuación, dé una fórmula en forma cerrada para la secuencia\(\{a_n:n \geq 0\}\) que representa.

a.\(e^{7x}\)

b.\(x^2e^{3x}\)

c.\(\dfrac{1}{1+x}\)

d.\(e^{x^4}\)

22. Encuentre el coeficiente encendido\(x^{10}/10!\) en cada una de las funciones generadoras exponenciales a continuación.

a.\(e^{3x}\)

b.\(\dfrac{e^x-e^{-x}}{2}\)

c.\(\dfrac{e^x+e^{-x}}{2}\)

d.\(xe^{3x}-x^2\)

e.\(\dfrac{1}{1-2x}\)

f.\(e^{x^2}\)

23. Encuentra la función generadora exponencial para el número de cadenas de longitud n formadas a partir del conjunto\(\{a,b,c,d\}\) si debe haber al menos una\(a\) y el número de\(c\)'s debe ser par. Encuentra una fórmula cerrada para los coeficientes de esta función generadora exponencial.

24. Encuentra la función generadora exponencial para el número de cadenas de longitud n formadas a partir del conjunto\(\{a,b,c,d\}\) si debe haber al menos una\(a\) y el número de\(c\)'s debe ser impar. Encuentra una fórmula cerrada para los coeficientes de esta función generadora exponencial.

25. Encuentra la función generadora exponencial para el número de cadenas de longitud\(n\) formadas a partir del conjunto\(\{a,b,c,d\}\) si debe haber al menos una\(a\), el número de\(b\)'s debe ser impar, y el número de\(d\) s es 1 o 2. Encuentra una fórmula cerrada para los coeficientes de esta función generadora exponencial.

26. Encuentra la función generadora exponencial para el número de cadenas alfanuméricas de longitud\(n\) formadas a partir de las 26 letras mayúsculas del alfabeto inglés y 10 dígitos decimales si

• cada vocal debe aparecer al menos una vez
• la carta\(T\) debe aparecer al menos tres veces
• la carta\(Z\) puede aparecer como máximo tres veces
• cada dígito par debe aparecer un número par de veces
• cada dígito impar debe aparecer un número impar de veces

27. Considerar la desigualdad

\(x_1+x_2+x_3+x_4 \leq n\)

donde\(x_1,x_2,x_3,x_4,n \geq 0\) están todos los enteros. Supongamos también que\(x_2 \geq 2\),\(x_3\) es un múltiplo de 4, y\(1 \leq x_4 \leq 3\). \(c_n\)Sea el número de soluciones de la desigualdad sujeta a estas restricciones. Encuentra la función generadora de la secuencia\(\{c_n:n \geq 0\}\) y úsala para encontrar una fórmula cerrada para\(c_n\).

Pista

Sí, esto está muy cerca del Ejercicio 8.8.7. Sin embargo, los límites\(x_4\) son diferentes aquí. Podrías intentar usar un sistema de álgebra computacional para agilizar la búsqueda de la expansión de fracciones parciales, la cual tendrá varios términos con cuya serie de potencias podrás trabajar rápidamente. Para el término que implica\(1/(1+x^2)\), elaborar la serie a mano. Usted puede encontrar que su solución a este problema tiene dos partes: una para cuando\(n\) es par y otra para cuando\(n\) es impar.

28. Probar la Proposición 8.3 sobre los coeficientes en el producto de dos funciones generadoras ordinarias.