He llegado a una fórmula más sencilla que sería la siguiente:
Siendo a el número de elementos a agrupar, b el número de elementos en cada grupo, y k el cociente entre a y b (que se supone entero), igual por tanto al número de grupos en cada combinación. Observa que en la fórmula b! está elevado a k
Por ejemplo, para a=9, b=3 se tendría k=3 y la fórmula saldría:
que es 280, coincidiendo con lo que esperabas. En cambio para los otros casos que ponías no me sale lo mismo. Para a=12, b=3 (se tendría k=4) se obtiene con mi fórmula 15400, mientras que tú decías que eran 1540 (curiosamente diez veces menor). Para a=30, b=6 (por tanto k=5) me salen 11.423.951.396.577.720 combinaciones, muy por encima de las 3.995.986.995 que tú decías (concretamente, me sale un factor 2858856 veces mayor)
Mi demostración
Mi idea parte de que agrupando a elementos de b en b, se pueden formar k=b/a grupos (suponiendo siempre que b es múltiplo de a)
- El primer grupo estará formado por cualquier combinación de b elementos a tomar entre todos los que hay. El número de tales combinaciones es C(a,b) (número combinatorio a sobre b, o coeficiente binomial)
- El segundo grupo estará formado otra vez por cualquier combinación de b elementos, pero esta vez no tenemos para elegir todos los a iniciales, pues ya se han usado b elementos en el primer grupo. Por tanto serían b elementos a elegir de un conjunto de (a-b), y por tanto sería el número binomial C(a-b, b)
- El tercer grupo, de forma análoga, serían b elementos a elegir entre (a-2b) elementos, y por tanto C(a-2b, b)
- Etc, en cada grupo se va rebajando el numerador del coeficiente binomial en b, hasta que el último grupo sería formado por b elementos a elegir entre (a-(k-1)b), y por tanto sería C(a-(k-1)b, b)
Escribiendo entonces la fórmula completa, el total de agrupaciones que pueden formarse saldría de multiplicar todos esos números combinatorios antes escritos, es decir:
Aquí podrían aparecer elementos repetidos según tu criterio, pues un grupo como (1,2,3) (4,5,6) (7,8,9) sería equivalente a (4,5,6), (1,2,3), (7,8,9) y otras similares. Pero si te das cuenta estos casos son en realidad permutaciones de los bloques. Ya que tenemos 3 bloques habrá 3! de esas permutaciones. En el caso general serían k!, por lo que basta dividir la fórmula anterior por k! para "eliminar" esos casos que se consideran iguales. Haremos esta división al final.
De momento vamos a intentar simplificar la fórmula. Para ello podemos recordar la definición de número combinatorio:
Si usamos esta definición para expandir la fórmula antes escrita, nos queda:
y ahora viene lo bueno. Si te fijas, en el denominador de la primera fracción aparece (a-b)!, que se simplifica con el numerador de la siguiente, y lo mismo pasa con su denominador (a-2b)! que se simplifica con el numerador de la siguiente, etc. por lo que al final queda:
En la última fracción aparece (a-kb)!, pero ya que kb es igual a a, esto es el factorial de cero, que por definición es 1, por lo que la expresión completa se reduce a:
Si ahora divides eso por k! para "eliminar" las permutaciones de grupos, ya que las consideras soluciones iguales, se llega a la fórmula inicial como se quería demostrar.
Listarlas todas con python
Estoy seguro de que tiene que haber una implementación más eficiente pero de momento sólo se me ha ocurrido lo siguiente:
- Generar todas las permutaciones de a elementos, con ayuda de
itertools.permutations
. Esta función es lazy lo que quiere decir que no genera todas las permutaciones cuando se la llama y retorna una lista con ellas, sino que lo que retorna es un generador en el que, cada vez que iteras, se recupera una nueva permutación. Por tanto es eficiente en memoria (aunque no en tiempo) porque a pesar de que hay muchas permutaciones de las que sólo aprovecharemos unas pocas, las que no aprovechamos no ocupan espacio porque las voy descartando.
- Para cada permutación, agrupo de b en b los elementos de la permutación. Formo así k grupos de b elementos cada uno.
- Cada grupo lo ordeno (para que si una vez me sale por ejemplo el grupo [1,2,3] pero en otra iteración me sale el [3,2,1], al final ambos acaben siendo el mismo, pues al ordenarlos sale [1,2,3] en ambos casos
- Convierto cada grupo en una tupla, y genero otra tupla con todos los grupos. De nuevo ordeno esta tupla de tuplas, para que el caso
((1,2,3), (4,5,6) , (7,8,9))
acabe siendo idéntico a ((4,5,6), (7,8,9), (1,2,3))
. Observa que ordeno la secuencia de tuplas, pero no el interior de cada tupla (que ya estaba ordenado de antes).
- Meto la tupla (de tuplas) resultante en un conjunto.
Ya que el conjunto va descartando duplicados, y debido a que las ordenaciones que hice de las tuplas acaban causando duplicados en las permutaciones equivalentes, al final el conjunto tendrá sólo las que buscas.
El código sería éste (la función grouper()
la tomé inspirada de una que aparece en la documentación del módulo itertools
).
from itertools import permutations
def grouper(lista, k):
args = [iter(lista)] * k
return zip(*args)
a = 9
b = 3
k = a//b
total = set()
for combinacion in permutations(range(a)):
aux = [tuple(sorted(grupo)) for grupo in grouper(combinacion, b)]
total.add(tuple(sorted(aux)))
print(len(total))
Y salen 280. Pero repito que no me parece muy eficiente tener que generar 9! (362.880) permutaciones para quedarse sólo con 280. Seguiré pensando...
Nota adicional
Tu fórmula y la mía no son equivalentes, aunque ambas dan el mismo resultado para a=9; b=3 (probablemente porque tú sabías que tenía que salir 280 en este caso y "apañaste" una fórmula que diera ese resultado). Curiosamente tu fórmula da también los mismos valores que la mía para otros números pequeños, como a=6, b=3 o a=8, b=4. No obstante en cuanto aumentas a por encima de 9 las fórmulas comienzan a dar valores diferentes.
Por ejemplo, para a=10, b=2, tu fórmula predice 63 combinaciones, pero el script python anterior genera 945, que son los predichos por mi fórmula. Con números mayores ya es difícil de verificar experimentalmente porque el script python se eterniza (es lo que tiene el factorial, crece más rápido aún que la exponencial).