Es fundamental entender el código de forma correcta antes de usarlo a tu proyecto si ttienes algo que aportar puedes decirlo en los comentarios.
Solución:
En la “Actualización” (el día posterior a la publicación de la Pregunta), el OP menciona una recursividad para contar las particiones de $n$ en $k$ partes distintas, cada parte como máximo $M$:
$$ p_k(leq M, mathcalD,n) = p_k-1(leq M-1, mathcalD,nk) + p_k(leq M-1, mathcal D,nk) $$
y pregunta “¿Cómo puedo probar esto?”.
Para ver esto, separe las particiones requeridas en función de si $1$ aparece como sumando. Si es así, restar $1$ de cada sumando produce una partición de $nk$ con exactamente $k-1$ partes distintas (dado que el sumando original $1$ desaparece), cada parte como máximo $M-1$. Estas particiones se cuentan por el primer término del lado derecho de la recursividad. De lo contrario, el sumando $1$ no aparece, y restando $1$ de cada parte resulta una partición de $nk$ con exactamente $k$ partes distintas, cada parte como máximo $M-1$. Estos casos se cuentan por el segundo término.
Tenga en cuenta que existe una partición de $n$ con $k$ partes distintas si y solo si $n ge binomk+12$, porque los sumandos ascendentes $m_1 + ldots + m_k = n$ deben satisfacer $m_i ge i$. Si $n = binomk+12$, entonces solo hay una de esas particiones con $k$ partes distintas, la mayor de las cuales es $k$. La aplicación repetida de la recursividad culminará con términos que podemos evaluar “por inspección” como cero o como uno.
Por sí misma, esta recursión no parece brindarnos una forma especialmente atractiva de evaluar $p_k(leq M, mathcalD,n)$. Al igual que la recursividad de los números de Fibonacci, como método de arriba hacia abajo, adolece de volver a calcular los términos varias veces (dando una complejidad exponencial), por lo que sería mejor trabajar con él como un método de abajo hacia arriba (dando una complejidad polinomial).
Mejor para grandes parámetros es cerrar el círculo con las ideas presentadas por @NikosM. mostrando cómo la evaluación de $p_k(leq M, mathcalD,n)$ puede reducirse a contar particiones restringidas sin que requieren sumandos distintos.
Apuntalar. Supongamos que $n gt binomk+12$. Entonces los siguientes son iguales:
$(i)$ el número de particiones de $n$ en exactamente $k$ partes distintas, cada parte como máximo $M$, es decir, $p_k(leq M, mathcalD,n)$
$(ii)$ el número de particiones de $n – binomk2$ en exactamente $k$ partes, cada parte como máximo $M$
$(iii)$ el número de particiones de $n – binomk+12$ en como máximo $k$ partes, cada parte como máximo $M$
Bosquejo de la prueba: Una vez que sabemos que los sumandos ordenados de las particiones en $(i)$ satisfacen $m_i ge i$, es fácil visualizar sus equivalentes en $(ii)$ y $(iii)$ mediante cuadros de Young, también llamados Diagramas de Ferrers. Eliminamos un “triángulo base” de puntos correspondientes a los primeros $i$ puntos en el $i$ésimo sumando (ya que $m_i ge i$) para obtener el caso $(iii)$, y eliminamos un punto menos en cada sumando para conservar exactamente $k$ sumandos en el caso $(ii)$. Estas construcciones son reversibles y los recuentos son iguales.
Observación 1 Si $n le binomk+12$, $p_k(leq M, mathcalD,n)=1$ si $n=binomk+12$ y $k le M$ y en caso contrario $p_k(leq M, mathcalD,n)=0$.
Observación 2 Para $k,n$ fijos, suponga que $M_0 = n – binomk2 gt 0$. Entonces para todo $M ge M_0$, $p_k(leq M, mathcalD,n) = p_k(leq M_0, mathcalD,n)$. Es decir, aumentar aún más el límite superior $M$ en el tamaño de las partes no generará particiones adicionales de $n$ con exactamente $k$ partes distintas.
Lectura recomendada
Andrews, Jorge E. La teoría de las particiones (Prensa de la Universidad de Cambridge, 1998)
Un clásico moderno de la teoría de particiones de enteros, revisado por Richard Askey en BAMS.
Existe un algoritmo para contar y generar particiones numéricas restringidas (tanto en mayor parte como en número de partes) en el libro de F. Ruskey Generación combinatoria (pág. 95) Segundo. 4.8 Particiones Numéricas:
Definir $P(n; k; s)$ ser el conjunto de todas las particiones de $n$ en $k$
partes con la mayor parte igual a $s$y deja $p(n; k; s) = left|P(n; k; s)right|$. Claramente, para tener $p(n; k; s) > 0$ debemos tener al menos una parte igual a $s$ y como mucho $k$ partes iguales a $s$. Por lo tanto $s + k le n le ks$.Clasificando las particiones de $P(n; k; s)$ de acuerdo con el valor de la segunda parte más grande, llámela $j$, obtenemos la siguiente relación de recurrencia, que no tiene términos cero; es una relación de recurrencia positiva.
$$p(n; k; s) = sum^min(s,ns-k+2)_j=max(1,lceilfracnsk-1rceil )p(ns;k-1;j) tag4.35$$
Comentarios y calificaciones
Tienes la opción de añadir valor a nuestro contenido informacional asistiendo con tu veteranía en las críticas.