Combinaciones de un tamaño específico para sumar un N específico

Question

Estoy buscando una manera, para cualquier N, de generar todas las combinaciones (definitivamente no permutaciones) de tamaño N, que suman a N-1, involucrando (incluyendo la repetición) 0 a N-1, donde N >= 3.

Por ejemplo, para N=2, entonces una combinación (de tamaño 2) de sólo 0 y 1 que sume 1. Esto fue bastante simple para mí, pero rápidamente me perdí al tratar de decidir cuántos eran válidos para N=3 o N=4, por no hablar de determinar un algoritmo o fórmula sin sólo lanzar un programa de ordenador en el problema y mirar la salida y tratar de adivinar uno.

Estoy bastante seguro de que hay menos de N^2, ya que hay N variables y cada una puede ser de 0 a N-1, pero como busco combinaciones y no permutaciones, algunas se eliminan. También estoy bastante seguro de que, como mínimo, hay 1 combinación válida para cada solución, porque podría tener simplemente 0,0,.... N-1. También estoy bastante seguro de que claramente menos de la mitad de ellos van a ser válidos, porque la otra mitad es fácilmente va a llegar a más de N-1, y mucho del resto no va a llegar allí, por lo que instintivamente, voy a decir que para cualquier N, va a ser bastante pequeño, en relación con N. Pero no tengo idea de cómo ir sobre la cuantificación de este.

¿Alguna sugerencia?]

Edit: Lo siento chicos- estoy buscando tanto generar todas las combinaciones, como, implícitamente, saber cuántas hay (sería bastante difícil generarlas sin poder contarlas).

Edita un poco más: OK. He estado mirando el Partición cosa, y se acerca bastante a lo que busco, pero aún me fallan un par de detalles.

En primer lugar, la partición de N no es exactamente lo que estoy buscando: el rango es de 1 a N, con un objetivo de N, a diferencia de 0 a N-1, con un objetivo de N-1, y sólo estoy interesado en las particiones con un tamaño de N. Estoy pensando que los dos deben ser convertibles sin demasiado esfuerzo: si busco las particiones de N-1, y sólo relleno las ranuras vacías con cero, entonces debería obtener lo que estoy buscando, ¿verdad?

En segundo lugar, la página de la Wiki que aparece da funciones para aproximar o calcular el número de particiones para cualquier N. Todavía no estoy del todo seguro de cómo haría para generando las particiones. Mirando la estructura de las particiones para el 8, por ejemplo, parece que no debería ser demasiado difícil. Estaba pensando en dividir el objetivo original en compuestos de dos componentes, por ejemplo, de {7, 1} a {1, 7}. Luego, siempre que exista un valor a la derecha que no sea 1, desglosarlo recursivamente, y contar como válidos todos aquellos donde aparezcan en orden descendente de izquierda a derecha. Parece que esto debería funcionar-¿Opiniones?

Answer 1

Si los diferentes pedidos no se cuentan como diferentes entonces esto es de hecho el Función de partición ya que cualquier partición de $N-1$ no tiene más que $N-1$ partes positivas y puede utilizar $0$ s para rellenar los huecos. Tienes que compensar, pero la secuencia comienza 1, 1, 2, 3, 5, 7, 11, 15, ...

Añadido: Es bastante fácil calcular el número de particiones y generarlas utilizando el programa R partitions paquete. Por ejemplo (adaptado para los detalles de esta pregunta)

> library(partitions)
> N <- 8
> P(N-1)
[1] 15
> t(rbind(parts(N-1),0))
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
 [1,]    7    0    0    0    0    0    0    0
 [2,]    6    1    0    0    0    0    0    0
 [3,]    5    2    0    0    0    0    0    0
 [4,]    5    1    1    0    0    0    0    0
 [5,]    4    3    0    0    0    0    0    0
 [6,]    4    2    1    0    0    0    0    0
 [7,]    4    1    1    1    0    0    0    0
 [8,]    3    3    1    0    0    0    0    0
 [9,]    3    2    2    0    0    0    0    0
[10,]    3    2    1    1    0    0    0    0
[11,]    3    1    1    1    1    0    0    0
[12,]    2    2    2    1    0    0    0    0
[13,]    2    2    1    1    1    0    0    0
[14,]    2    1    1    1    1    1    0    0
[15,]    1    1    1    1    1    1    1    0

Si quisieras hacerlo tú mismo, podrías utilizar el siguiente algoritmo para las particiones de $N-1$

1. poner los números $1$ a $N-1$ en la primera columna (así $N-1$ filas inicialmente)
2. calcular la diferencia $d$ entre $N-1$ y la suma de los números de esa fila
3. si $d=0$ y luego llenar el resto de la fila con $0$ s y luego STOP para esa fila
4. para otras filas con $d>0$ sustituye cada fila por otras idénticas hasta ese punto pero con un número extra de $1$ al menor de $d$ o el número más pequeño utilizado hasta ahora en esa fila
5. volver a a 2