Buenas,
Alguno hizo el ejercicio Partitions with summands bounded in number and size? Tengo una duda y capaz me la puede contestar.
Saludos
Yo lo estaba haciendo, pero la verdad me di cuenta(tarde) que estaba re perdidio con este,
Ayer bien de noche le mande mail al tuba a ver si me tiraba algun pique dado que se me hizo la fecha,
Que duda tenes? obviamente no prometo nada, pero capaz con algo de lo que lei buscando ayuda o de lo que se me ocurrio, pueda complementarte.
Saludos!
Es un ejercicio interesante, pero hay que pensar bastante y se aprende mucho, especialmente en cuando a forma de pensar en este tipo de problemas.
La manera combinatoria más clara de resolverlo, involucra el uso de funciones multivariadas, pero lo vamos a ver al final del curso. Aquí la clave es que dice que hay que pensar de manera recursiva (léase, demostrar por inducción).
Le doy una idea de cómo lo pensé, pero van a tener que completar bien con detalles. Está relacionado con interpretaciones combinatorias de las funciones generatrices que vimos en clase (y que es parte fundamental del contenido del curso).
Si ven la generatriz, se simplifica a (1-z^(k+1))*...*(1-z^(k+l))/((1-z)*..*(1-z^l)).
El resultado es simétrico en k y l.
Vamos a suponer ahora que agregamos sumandos de tamaño (l+1). Entonces, siguiendo con la metodología de la clase, implica agregar una secuencia de elementos de tamaño (l+1), con lo cual en la generatriz, hay que multiplicar por 1/(1-x^(l+1)).
El problema es que entonces puede suceder que agregue muchos factores l+1, y entonces tenga más de k sumandos (a lo sumo puedo usar k sumandos). Entonces, hay que restar toda contribución que haga que haya más de k sumando.
Sabemos por inducción (hay que hacer bien la demostración por inducción, asumiendo como paso base que son sólo sumandos de tamaño 1) que la generatriz cuenta todas las particiones de a lo sumo k sumandos, cada uno a lo sumo con valor l. Ahora, si permitimos que haya de valor l+1, está bien multiplicar por 1/(1-x^(l+1)), pues es una secuencia de sumandos de tamaño l+1, pero el problema es que tenemos que restar toda contribución que involucre más de k sumandos.
Pregunta, ¿porqué voy a agregar más de k sumandos? Bueno, esto sólo puede venir por la secuencia que acabo de agregar, dado que por hipótesis de inducción, cuando usaba sumandos hasta l, no ítena más de k sumandos. Así que debo restar todos las particiones que tengan más de k sumandos, sabiendo que uno o más de ellos es l+1. Bueno, cada uno de los sumandos anteriores aporta al menos 1 (pues los sumandos como mínimo valen 1). Con lo cual z^k implica que al menos uso k sumandos (pues cada uno tiene tamaño 1). Yo se que por hipótesis de inducción, ningún sumando anterior tenía más de k elementos, así qeu a lo sumo voy a tener z^k por este motivo.
¿Que le tengo que agregar a z^k? Le tengo que agregar una secuencia NO vacía (al menos un sumando debe ser l+1) de sumandos de valor l+1. Entonces la secuencia no vacía da el factor A(z) = z^(l+1)/(1-z^(l+1)) y el valor que tengo es z^k * A(z). Esto se lo debo restar, dando el valor -z^(k+l+1) en el numerador, que jugo con el 1/(1-z^(l+1)) que agregaba me da el (1-z^(k+1+1))/(1-z^(l+1)) de la demostración por inducción.
Espero que esta ayuda haya sido de utilidad. Es un problema interesante y que enseña muchas cosas sobre la manera de pensar estos problemas.
Tuba.
La manera combinatoria más clara de resolverlo, involucra el uso de funciones multivariadas, pero lo vamos a ver al final del curso. Aquí la clave es que dice que hay que pensar de manera recursiva (léase, demostrar por inducción).
Le doy una idea de cómo lo pensé, pero van a tener que completar bien con detalles. Está relacionado con interpretaciones combinatorias de las funciones generatrices que vimos en clase (y que es parte fundamental del contenido del curso).
Si ven la generatriz, se simplifica a (1-z^(k+1))*...*(1-z^(k+l))/((1-z)*..*(1-z^l)).
El resultado es simétrico en k y l.
Vamos a suponer ahora que agregamos sumandos de tamaño (l+1). Entonces, siguiendo con la metodología de la clase, implica agregar una secuencia de elementos de tamaño (l+1), con lo cual en la generatriz, hay que multiplicar por 1/(1-x^(l+1)).
El problema es que entonces puede suceder que agregue muchos factores l+1, y entonces tenga más de k sumandos (a lo sumo puedo usar k sumandos). Entonces, hay que restar toda contribución que haga que haya más de k sumando.
Sabemos por inducción (hay que hacer bien la demostración por inducción, asumiendo como paso base que son sólo sumandos de tamaño 1) que la generatriz cuenta todas las particiones de a lo sumo k sumandos, cada uno a lo sumo con valor l. Ahora, si permitimos que haya de valor l+1, está bien multiplicar por 1/(1-x^(l+1)), pues es una secuencia de sumandos de tamaño l+1, pero el problema es que tenemos que restar toda contribución que involucre más de k sumandos.
Pregunta, ¿porqué voy a agregar más de k sumandos? Bueno, esto sólo puede venir por la secuencia que acabo de agregar, dado que por hipótesis de inducción, cuando usaba sumandos hasta l, no ítena más de k sumandos. Así que debo restar todos las particiones que tengan más de k sumandos, sabiendo que uno o más de ellos es l+1. Bueno, cada uno de los sumandos anteriores aporta al menos 1 (pues los sumandos como mínimo valen 1). Con lo cual z^k implica que al menos uso k sumandos (pues cada uno tiene tamaño 1). Yo se que por hipótesis de inducción, ningún sumando anterior tenía más de k elementos, así qeu a lo sumo voy a tener z^k por este motivo.
¿Que le tengo que agregar a z^k? Le tengo que agregar una secuencia NO vacía (al menos un sumando debe ser l+1) de sumandos de valor l+1. Entonces la secuencia no vacía da el factor A(z) = z^(l+1)/(1-z^(l+1)) y el valor que tengo es z^k * A(z). Esto se lo debo restar, dando el valor -z^(k+l+1) en el numerador, que jugo con el 1/(1-z^(l+1)) que agregaba me da el (1-z^(k+1+1))/(1-z^(l+1)) de la demostración por inducción.
Espero que esta ayuda haya sido de utilidad. Es un problema interesante y que enseña muchas cosas sobre la manera de pensar estos problemas.
Tuba.
Muchas gracias!
Pense (erroneamente) que la inducción no era la manera mas "combinatoria" de resolución, pero por lo visto, se puede usar de una manera combinatoria con los argumentos adecuados. Voy a tratar de complementar adecuadamente,muchas gracias de nuevo!!!
Saludos!