Autor Tema: Funciones generadoras

0 Usuarios y 1 Visitante están viendo este tema.

26 Octubre, 2010, 04:40 pm
Leído 1772 veces

bailarin_log

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Masculino
Hola chicos,

Quien puede ayudarme con este problema, llevo días dándole vueltas.

¿De quantes maneres podemos distribuir 100 estudiantes en seis aulas si no hacemos distinción entre estudiantes, y la capacidad máxima de las aulas es de 40, excepto una que tiene una capacidad máxima de 20 estudiantes? Resolver este ejercicio utilizando funciones generadoras.


Saludos.

26 Octubre, 2010, 06:44 pm
Respuesta #1

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
En 5 de las 6 aulas pueden haber a lo más 40 alumnos.  Por tanto \( (1+x+x^2+\cdots+x^{40})^5 \) es un factor del polinomio buscado.
En el aula 6 pueden haber a lo más 20.  Por tanto, \( (1+x+x^2+\cdots+x^{20}) \) es el otro factor del polinomio.

Ergo, el polinomio generadores es \( f(x)=(1+x+x^2+\cdots+x^{40})^5(1+x+x^2+\cdots+x^{20}) \).  Finalmente, lo que buscas es el coeficiente de \( x^{100} \).

Concluye.
Saludos.

27 Octubre, 2010, 01:11 pm
Respuesta #2

bailarin_log

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Masculino
Oye hector manuel muchísimas gracias, ya lo he resuelto porque lo que tenía duda era en el planteamiento.

Saludos.

28 Octubre, 2010, 09:02 am
Respuesta #3

bailarin_log

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Masculino
Y en este ejercicio como podría sacar la función generadora.

Decir que función generadora utilizaríamos  y que término de la función necesitaríamos (sin calcularlo), para encontrar el número de soluciones de la ecuación.

\( x_1+2x_2+3x_3=40; \) con \( x_1,x_2 ,x_3\geq{0} \)

Saludos.

28 Octubre, 2010, 10:06 am
Respuesta #4

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 ¿Lo has intentado?.

 En lenguaje de funciones generadoras estamos diciendo que tres exponentes, uno de ellos cualesquiera, otro impar y un tercero múltiplo de tres deben de sumar \( 40 \).

 Eso nos lleva a considerar polinomios:

\(  1+x+x^2+x^3+x^4+\ldots \)

\(  1+x^2+x^4+x^6+x^8+\ldots \)

\(  1+x^3+x^6+x^9+x^{12}+\ldots \)

 Concluye...

Saludos.

28 Octubre, 2010, 12:20 pm
Respuesta #5

bailarin_log

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Masculino
Como el enuciado dice que no hace falta calcularlo, se quedaría así, es la función generadora así:

\(  1+x+x^2+x^3+x^4+\ldots \)

\(  1+x^2+x^4+x^6+x^8+\ldots \)

\(  1+x^3+x^6+x^9+x^{12}+\ldots \)

\( g_4_0=(1+x+x^2+x^3+x^4+\ldots+x^4^0)(1+x^2+x^4+x^6+x^8+\ldots+x^4^0)(1+x^3+x^6+x^9+x^12+\ldots+x^3^9) \)

Saludos.

28 Octubre, 2010, 02:38 pm
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Si; supongo que ese \( g_{40} \) se refiere a que tienes que tomar el coeficiente del \( x^{40} \) del producto de polinomios que pones a continuación.

Saludos.

29 Octubre, 2010, 09:29 am
Respuesta #7

bailarin_log

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

si eso es, yo lo expreso así \( g_4_0 \)pero si me refiero al \( x^4^0 \).

Gracias y saludos.

08 Noviembre, 2010, 09:37 am
Respuesta #8

neptu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 1
  • Karma: +0/-0
  • Sexo: Femenino
Hola,

    Respecto al mensaje anterior que vuelvo a poner aquí no me queda nada claro como se calcula el coeficiente de \( x^{100} \) alguien me lo puede
demostrar paso a paso.

En 5 de las 6 aulas pueden haber a lo más 40 alumnos.  Por tanto \( (1+x+x^2+\cdots+x^{40})^5 \) es un factor del polinomio buscado.
En el aula 6 pueden haber a lo más 20.  Por tanto, \( (1+x+x^2+\cdots+x^{20}) \) es el otro factor del polinomio.

Ergo, el polinomio generadores es \( f(x)=(1+x+x^2+\cdots+x^{40})^5(1+x+x^2+\cdots+x^{20}) \) .  Finalmente, lo que buscas es el coeficiente de \( x^{100} \) .

08 Noviembre, 2010, 02:08 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Para ser sincero tampoco tengo claro una manera efectiva de calcular dicho coeficiente; sé que hay algunas técnicas que facilitan su cálculo en algunos casos pero no las domino.

 En general y como consecuencia del desarrollo de Taylor, el coeficiente  de \( x^n \) del polinomio \( f(x) \) es:

\(  \dfrac{f^{n)}(0)}{n!} \)

 Pero las cuentas no son tan fáciles; también suele usarse que:

\(  (1+x+x^2+x^3+\ldots)=\dfrac{1}{1-x} \)

 y
 
\(  (1+x+x^2+\ldots+x^n)=\dfrac{1-x^{n+1}}{1-x} \)

 Pero eso no siempre simplifica la cuestión.

 En tu caso uno puede resolver el problema sin funciones generatrices así. Nos preguntan las soluciones enteras de:

\(  x_1+x_2+x_3+x_4+x_5+x_6=100 \)

 con \( 0\leq x_1,x_2,x_3,x_4,x_5\leq 40 \) y \( 0\leq x_6\leq 20 \).

 Por el principio de inclusión-exclusión, esto equivale a:

 Soluciones con todos los \( x_i\geq 0 \),

 menos soluciones con algún \( x_i\geq 41 \), \( 1\leq i\leq 5 \) o \( x_6\geq 21 \).

 mas soluciones con dos \( x_i\geq 41 \), \( 1\leq i\leq 5 \) o un \( x_i\geq 41 \) y \( x_6\geq 21 \)

 Finalmente es fácil ver que eso corresponde a:

\(  CR_{6,100}-5CR_{6,100-41}-CR_{6,100-21}+\displaystyle\binom{5}{2}CR_{6,100-41-41}+5CR_{6,100-41-21} \)

 con:

\(  CR_{n,m}=\displaystyle\binom{n+m-1}{m} \)

Saludos.