Número de combinaciones con restricciones

Question

Así que lo ideal sería una solución general (o una explicación de cómo llegar a ella) para el siguiente problema, que circunscribiré en un contexto para facilitar su acceso.

Considere $n$ tarros indistinguibles, $a$ canicas indistinguibles etiquetadas como "A" y $b$ canicas indistinguibles etiquetadas como "B". Los números $a\geq 0$ y $b\geq 0$ mismos ya vienen restringidos a cumplir los siguientes requisitos:

$$a -b \geq 0 \quad \text{and} \quad 3b-a+1\geq 0 $$

Las canicas se pueden distribuir en el $n$ con dos restricciones para el número final de "A" ( $x$ ) y "B" ( $y$ ) que terminan en el mismo frasco: $$ x-y \geq 0\quad\text{and}\quad 3y-x+1 \geq 0 $$

Necesito una expresión general para el número $m$ de combinaciones posibles $$m=f(n,a,b)$$ o si eso no es posible, necesito al menos las soluciones específicas para $n=3$ y $n=4$ .

Además, sería estupendo que hubiera una forma calculada de etiquetar el $n$ tarros según su "contenido" para cada combinación $m$ Por ejemplo $$ \begin{Bmatrix} [x_{11}][y_{11}] & [x_{12}][y_{12}] & ... & [x_{1n}][y_{1n}] \\ [x_{21}][y_{21}] & [x_{22}][y_{22}] & ... & [x_{2n}][y_{2n}] \\ ...& ...& ... & ... \\ [x_{m1}][y_{m1}] & [x_{m2}][y_{m2}] & ... & [x_{mn}][y_{mn}] \end{Bmatrix}$$ para que cada $\alpha_{ij}=f(o,p,a,b)$ y $\beta_{ij}=f(o,p,a,b)$ con $o=1,2,...,m$ y $p=1,2,...,n$ .

Soy químico y no tengo conocimientos muy profundos de matemáticas, así que perdonen la incompetencia que pueda mostrar. Mi mayor problema ahora mismo es cómo implementar las restricciones en los cálculos combinatorios. En caso de que no haya una forma analítica de derivar una solución general, ¿alguna pista sobre un procedimiento algorítmico que pueda hacer el trabajo para, digamos $a,b<50$ también se agradecería.

Answer 1

Hice un programa que parece funcionar. Comienza a ser lento cuando los números de entrada se acercan a $50$ y, por lo tanto, tardó más de un minuto en encontrar que $f(15,40,30)= 25,228,180$ . Pero entonces no he optimizado y sólo estoy usando Visual Basic.

De todos modos, el algoritmo básico es el siguiente...

Paso 1: Generar la siguiente partición de $a$ con $n$ o menos piezas

Como ningún frasco puede tener más $B$ canicas que $A$ canicas, el número máximo de tarros posible es $a$ . Dado $n \le a$ tarros, el número total de maneras de distribuir $a$ canicas entre $n$ o menos tarros es sólo el número de particiones de $a$ con $n$ o menos partes. En la red se pueden encontrar algoritmos para determinar dichas particiones. El que yo he utilizado es el siguiente aquí .

Paso 2: Asignar el mínimo $B$ canicas a cada frasco

Podemos calcular el número mínimo de $B$ canicas que cada frasco con $A$ las canicas deben contener al menos. Distribuya las $B$ canicas y reducir $b$ por el total distribuido. Cuando $b$ es pequeño, puede que no sea posible distribuir ni siquiera el mínimo. En ese caso, no hay solución posible para esa partición, y vamos al Paso 1.

Paso 3: Distribuir cualquier exceso $B$ canicas a la partición

Este es el paso más difícil, así que lo he dividido en subpasos. Antes de continuar, debo mencionar que si no hay exceso de $B$ canicas, la partición sólo tiene una solución, y vamos al paso 1.

Paso 3a: Agrupar tarros con el mismo número de $A$ mármoles

Si tenemos dos tarros con cuatro $A$ canicas cada uno (y por lo tanto un mínimo $B$ mármol cada uno), no queremos contar las combinaciones en las que el primer tarro recibe dos excesos $B$ canicas y el segundo recibe una, a diferencia de las combinaciones en las que el primer tarro recibe una y el otro dos. Por lo tanto, debemos agrupar los tarros con el mismo número de $A$ canicas en un grupo, antes de distribuir $B$ canicas. El máximo de cada grupo será "Número de tarros con igual $A$ canicas" $\times$ ("Máximo $B$ canicas en un frasco con $x$ $A$ canicas" menos "Mínimo $B$ canicas en un frasco con $x$ $A$ canicas")

Paso 3b: Generar cada una de las posibles distribuciones del exceso $E$ a los grupos

Si tenemos $k$ grupos, cada uno con una capacidad máxima $C_i$ , donde $i \le k$ y $x_i$ es el número de $B$ canicas asignadas al grupo $i$ queremos un algoritmo que genere todas las soluciones posibles para $x_1+x_2+...+x_k=E$ . Me llevó un tiempo encontrar dicho algoritmo. El algoritmo es básicamente este:

1. Llenar cada grupo con el máximo (si es posible), empezando por el grupo $1$ (la izquierda).
2. En el grupo en el que has terminado, mueve una canica hacia la derecha, si es posible. Esa es una nueva combinación. Y has terminado en un nuevo grupo. Ve a $2$
3. Si no es posible mover una canica hacia la derecha, ve hacia atrás hasta que encuentres un grupo en el que sea posible mover una canica adicional hacia la derecha o hasta que ya no puedas moverte hacia atrás.

A continuación se muestra un ejemplo con $E=3$ y cuatro grupos con las capacidades $4,3,3,1$ :

Paso 3c: Para cada distribución, determine de cuántas maneras el $B$ Las canicas asignadas a cada grupo pueden distribuirse entre los tarros de ese grupo. Multiplica el número de cada grupo y súmalo al total.

Cuando tengas una distribución de las canicas sobrantes entre los grupos, tienes que determinar de cuántas maneras cada asignación de $B$ las canicas a un grupo se pueden distribuir realmente entre los miembros del grupo, sin repeticiones. Así, si se tuviera $4$ de un grupo, donde la capacidad máxima de cada miembro del grupo era $4$ y que había asignado $8$ exceso de canicas al grupo, las posibles distribuciones serían

Vemos que este algoritmo no es más que una versión modificada del de $3b$ . Sólo que la capacidad máxima de cada miembro es la misma y el criterio para mover una canica a la derecha no es sólo que haya suficiente capacidad a la derecha, sino que el número resultante de $B$ canicas a la derecha es menor o igual que el número a la izquierda.

Paso 4: Ir al paso 1 hasta que la última partición haya sido tratada

Creo que no he explicado bien el algoritmo, así que no dudes en hacer preguntas. Puedo publicar el código si lo deseas, pero te advierto que no está comentado.