[Héctor Manuel]

Hola amigos. Tenía mucho tiempo sin participar aquí. La pregunta que tengo he intentado resolverla por varias maneras, pero no he podido. Por eso vengo a pedir su ayuda.

¿Cuál es el número de soluciones enteras no negativas de la ecuación  \( x_1+x_2+\cdots+x_n=t \) tales que \( x_1\ge x_2\ge x_3\ge\cdots\ge x_n  \) ?


El problema es fundamentalmente que la restricción impuesta evita que pueda hacer uso de técnicas elementales de conteo. ¿Que sugieren?

Saludos, Héctor.

[Phicar]

Hola, pues es que eso es la definicion de particion de un numero t en n sumandos.(Mira en wikipedia) hay formas recursivas y dinamicas de generarlos pero es un problema NP..
Hay un trabajo interesante que es relativamente nuevo sobre las particiones link

[Héctor Manuel]

Mira.  El problema no es mío. Es de un amigo mío.  Pensando un poco le di la misma idea que tú a mí, pero ahora me ha dicho que no sólo le interesa conocer el número de soluciones, sino cuáles son.

Es decir, hacer un algoritmo óptimo, en el sentido de tiempo de cómputo, que le de explícitamente las soluciones.

Si sabes de algo de eso, ya que hace dos días estuvimos largo tiempo en la red buscando sin hallar nada, te lo agradeceremos (y más mi amigo)

Saludos.

[Phicar]

Pues el algoritmo que conozco para las soluciones es recursivo pero en t=100 ya se queda...basicamente es fuerza bruta y se usa la recursividad porque no se tiene control de n...Algo como

Particiones(int t,int n,Set v){
if(n==0 && t==0) {imprime(v);retorna;}
if(t==0 || n==0)retorna;
for(i=1;i<=t;i++)
Particiones(t-i,n-1,v=v U {i});//osea i hace ahora parte del conjunto v(que sera el que quede con los sumandos)
}


Ademas de eso, solo estaria el algoritmo dinamico que es basicamente usar la particion que se encuentre de t para generar la de t+1

Algo asi como las particiones de 4=3+1,2+2,2+1+1,1+1+1+1...y las de 5 son todas las anteriores mas un uno ademas de 3+2...
Osea que el paso(inductivo) seria que al tener t se tienen las particiones que contienen 1's de t+1...

Mas no puedo ayudar, por ignorancia :S