Supongamos que f (a, b, c) se define como el número de composiciones débiles (particiones ordenadas que permiten ceros) de a en exactamente b partes con cada parte no mayor que c. ¿Qué fórmulas recursivas satisface esta función?

Answer 1

Una fórmula recursiva que encontré es:
f (a, b, c) = f (a, b, c-1) + b * f (ac, b-1, c)

Prueba:

Sea F (a, b, c) el conjunto de todas las composiciones débiles de las partes a en b con cada parte no mayor que c. Cada elemento en F (a, b, c) tiene una parte de tamaño c o no. Si no tiene parte de tamaño c, es un elemento de F (a, b, c-1). Si tiene una parte de tamaño c, elimine esa parte para crear un elemento de F (ac, b-1, c). Tenga en cuenta que hay exactamente b elementos de F (a, b, c) que corresponden a cada elemento de F (ac, b-1, c) porque puede eliminar la parte del tamaño c de cualquiera de las posiciones b. Por lo tanto | F (a, b, c) | = | F (a, b, c-1) | + b * | F (ac, b-1, c) |, entonces:
f (a, b, c) = f (a, b, c-1) + b * f (ac, b-1, c)

Entiendo que esta prueba es un poco difícil de entender, por lo que si tiene problemas con ella, le recomiendo elegir algunos pequeños a, b, c y escribir los elementos de F (a, b, c) y luego construir F (a , b, c-1) y F (ac, b-1, c) usando los métodos anteriores solo para convencerse de que funciona.