Número de formas de distribuir objetos, algunos iguales y otros no, en grupos idénticos

Question

La pregunta que inicialmente pensó que se le pida que este era "cuántos entero cara cuboides hay con un volumen de $60^3$?".

Un pequeño ejemplo para aclarar: No se $3$ entero cara cuboides con un volumen de $8$, es decir,$8\times 1\times 1$, $4\times 2\times 1$, $2\times 2\times 2$.

Me di cuenta de que desde el primer factorización de $60^3$ es

$60^3=(2^2\times 3\times 5)^3=2^6\times 3^3\times 5^3$

Entonces el problema es equivalente a "¿de cuántas maneras distintas podemos distribuir $6$ objetos idénticos (es decir, el $2$s) y $3$ idénticos objetos de un tipo diferente (es decir, el $3$s) y $3$ idénticos objetos de un tipo diferente de nuevo (es decir, el $5$s) a $3$ idénticos a los grupos?"

Por ejemplo, $60^3=(2^4\times 3)\times (2\times 5^2)\times (2\times 3^2\times 5)$ sería una posible forma de paralelepípedo.

Tenga en cuenta que ninguna de las $3$ idénticos grupos se les permite estar vacía (es decir, una longitud lateral de $1$ en el paralelepípedo).

Para poner el problema de otra manera, ¿de cuántas maneras distintas podemos distribuir las letras de la palabra "AAAAAABBBCCC" a $3$ idénticos a los grupos?

He hecho venir para arriba con una solución, $475$, por una especie de método recursivo que yo inventé. Me han copiado mi solución a continuación. Se siente muy largo y complicado, por lo que me gustaría saber si hay una forma más rápida que se basa en algo más estándar de forma recursiva funciones definidas, y es más fácilmente generalizables. Soy consciente de que los problemas relacionados con el puede ser resuelto mediante Sterling números de la segunda clase, por ejemplo, o la Campana de los números. Pero no he sido capaz de encontrar ningún ejemplo de un problema como este, donde los objetos son una mezcla de idéntica y distinta (lo que debo llamar a esto? Clasificados?) y los grupos son idénticos.

Siéntase libre de NO leer, pero aquí está mi de largo aliento solución:

En primer lugar, ¿de cuantas formas hay para distribuir el 6 2s a través de los 3 grupos? Podemos enumerarlos:
0,0,6
0,1,5
0,2,4
0,3,3
1,1,4
1,2,3
2,2,2
Total: 7 formas

Ok, ahora ¿cuántas maneras existen para distribuir el 3 3s?
0,0,3
0,1,2
1,1,1
Total: 3 maneras

Esto significa que hay 7 x 3 = 21 formas de distribuir las 6 de la 2 y la 3 3s? No! Ya, lo que importa es que de los 7 distribuciones de 2s combinamos con cual de las 3 distribuciones de 3s.

La característica importante de una distribución, para ver cómo se combina con un conjunto de posibles distribuciones "superpuesto" en ella, es que los grupos (si los hubiera) se han realizado distinguibles unos de otros por la primera distribución. Hay 3 posibles patrones:

Todos los grupos indistinguibles (llamamos a esto)
Dos grupos indistinguibles, el otro distinguibles (llamar a este B)
Todos los grupos distinguibles (llamar a este C)

Volviendo a las 7 posibles distribuciones de 2 y etiquetado a, B o C de acuerdo a:
0,0,6 B
0,1,5 C
0,2,4 C
0,3,3 B
1,1,4 B
1,2,3 C
2,2,2 Un

Así que en total tenemos 1 A, 3 b y 3 Cs. En este punto podemos crear nuestra propia "álgebra" y el uso de una expresión algebraica-estilo de taquigrafía (teniendo en cuenta que a, B y C no representan números, pero los patrones):
A + 3B + 3C

Y para el 3 3s, tenemos:
0,0,3 B
0,1,2 C
1,1,1 Un
Haciendo A + B + C

Del mismo modo, para el 3 5s tendríamos a + B + C

Ahora, ¿cómo se combinan? Primero vamos a considerar la superposición de las 3 posibles distribuciones de los 3 a los 7 posibles distribuciones de 2s. Y supongamos que partimos de la superposición de un C-distribución (todos los 3 contenedores distinguibles) en otro C-distribución. Cuántos combinado de las distribuciones que hace que nos dan? Nos da 3 x 2 x 1 = 6. Y ¿cuáles son los patrones (a, B o C) para estas distribuciones? Todos ellos son de Cs. Y así, en nuestro casero álgebra, podemos introducir un símbolo * para la superposición de las distribuciones de los patrones, y decir:
C * C = 6C

Así que, ¿cuántas distribuciones que tenemos, y con lo que los patrones, mediante la superposición de la C 1-distribución de la 3 a la 3 C-distribuciones de 2s?
C * 3C = 18K

Ahora podemos ir a través de un proceso similar para la combinación de B con C, B con B, etc.

Tenga en cuenta que, desde Un patrón es equivalente a la pizarra en blanco que iniciamos, "multiplicar" por Una no tiene efecto:
A * C = C
A * B = B
A * A = A

Tenga en cuenta también que esta forma de "multiplicación" es conmutativa, es decir, B * C = C * B, etc, ya que vamos a obtener el mismo número de distribuciones de cualquiera de distribución "poner primero".

Algunos pensaron que nos dice que B * C = 3C, ya que si comenzamos con una C, hay 3 posibles lugares para la superposición de la distinguibles contenedor de la B.

Y por similar tipo de razonamiento, B * B = B + C

Ahora la combinación de todo juntos,

(A + 3B + 3C) * (A + B + C) = (A * A) + (A * B) + (A * C) + 3(B * A) + 3(B * B) + 3(B * C) + 3(C * A) + 3(C * B) + 3(C * C)

(Interesante notar que la distribución de la regla de "multiplicación" en este sentido es válido, ya que son la combinación de cada posible distribución de 2s con cada posible distribución de 3s)

= A + B + C + 3B + 3(B + C) + 9C + 3C + 9C + 18C
= A + 7B + 43 ° C

Todo lo que queda por hacer ahora es la superposición de las posibles distribuciones de las 5s: (A + 7B + 43 ° C) * (A + B + C)
= A + B + C + 7B + 43 ° C + 7(B * B) + 50(B * C) + 43(C * C)
= A + B + C + 7B + 43 ° C + 7B + 7C + 150 C + 258C
= UN + 15B + 459C

Lo que hace un total de 475 distintos aspectos.

Answer 1

Usando la notación de la siguiente MSE enlace Yo empezamos con el origen del conjunto múltiple

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \prod_{k=1}^l A_k^{\tau_k}$$

donde tenemos $l$ diferentes valores y sus multiplicidades son los $\tau_k.$ Nos preguntamos acerca de las distintas particiones de este conjunto múltiple en $N$ factores, incluyendo uno como un factor, donde diferentes se refiere a permutaciones de las $N$ factores por el grupo simétrico. En el caso de que uno no es admitida como un factor que fue discutido en la siguiente MSE enlace II.

Si tenemos un CAS como el Arce, $N$ es razonable y buscamos bastante instante de cálculo de estos valores, a continuación, puede utilizar el ciclo de índice $Z(S_N)$ del grupo simétrico que implementa la etiqueta operador $\textsc{MSET}_{=N}.$ Este rendimientos de la fórmula

$$\left[\prod_{k=1}^l A_k^{\tau_k}\right] Z\left(S_N; \prod_{k=1}^l \frac{1}{1-A_k}\right).$$

Aquí se utiliza la repetición por el Lovasz para el ciclo de índice $Z(S_N)$, que es

$A$Z(S_N) = \frac{1}{N} \sum_{i=1}^N a_l Z(S_{N-l}) \quad\text{donde}\quad Z(S_0) = 1.$$

Arce puede extraer de estos coeficientes preguntando por el coeficiente de de las correspondientes series de Taylor. Obtenemos la siguiente transcripción:

> FACTORES(60^3, 3);
475

> FACTORES(60^4, 3);
1710

> FACTORES(120, 4); 
20

> FACTORES(512, 4);
18

> FACTORES(729, 5);
10

> FACTORES(2^4*3^3*5^2, 6);
573

> seq(FACTORES(n,4), n=1..60);
1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2,

 1, 7, 2, 2, 3, 4, 1, 5, 1, 6, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1,

 4, 4, 2, 1, 11, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11

La secuencia es OEIS A218320 y se ve a tienen los valores de la derecha. El Arce aquí el código es bastante simple.

con(planta);
con(numtheory);

pet_cycleind_symm :=
proc(n)
opción de recordar;

 si n=0 entonces devolver 1; fi;

ampliar(1/n*
 agregar(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poli, ind)
local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 :=
[seq(polyvars[k]=polyvars[k]^olla,
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;


MSETS :=
proc(src, N)
local msetgf, cind, gf, cf;

 msetgf := mul(1/(1-A[q]), p=1..nops(src));
 cind := pet_cycleind_symm(N);

 gf := pet_varinto_cind(msetgf, cind);

 para la fq a nops(src) ¿
 gf := coeftayl(gf, [cf] = 0, src[cf]);
od;

gf;
end;

FACTORES :=
proc(n, N)
local mults;

 mults := map(el -> el[2], op(2, ifactors(n)));
 MSETS(mults, N);
end;

Observación. Una observación. Mientras Burnside y Polya sin duda representan un enriquecimiento aquí también hay que tener cuidado de incluir la conceptos básicos, que en este caso consiste en una simple recurrencia que es dado en la OEIS entrada y que calcula los valores deseados casi al instante. Con las variables cambiado de nombre para indicar la semántica tenemos una algoritmo de cuya exactitud de la siguiente manera por la inspección y que se muestra a continuación.

FACTREC :=
proc(val, numel, maxfact)
opción de recordar;
local divs;

 si numel = 1 entonces
 return `si`(val <= maxfact, 1, 0);
fi;

 divs := seleccionar(d -> d <= maxfact, divisores(val));
 agregar(FACTREC(val/d, numel-1, d), d en divs);
end;

FACTORSX := (n, N) -> FACTREC(n, N, n);

Answer 2

Este problema puede ser resuelto por una aplicación de Burnside del lexema.

Deje $X = \{(x,y,z) \in \mathbb N^3 : xyz = 60^3\}$ ser el conjunto de todas las formas de especificar el cuboides donde el orden de los lados no importa. El grupo $G = S_3$ actúa sobre los elementos de $X$ por permuting la orden de triple $(x,y,z)$. Estamos buscando el número de órbitas $|X/G|$.

Para ello, se calcula el número de elementos de a $X$ fijo por cada elemento de a$G$, y el promedio de ellos:

• $X^e$, el conjunto de los elementos fijados por el elemento de identidad $e$, es sólo $X$. Tenemos $|X| = |X^e| = \binom82 \binom52 \binom52$ mediante la aplicación de las estrellas y las barras para cada uno de los factores primos.
• $X^{(1\;2)}$, el conjunto de los elementos fijados por la transposición $(1\;2)$. Hay $4$ posibilidades de los poderes de $2$: $(2^3,2^3,1)$, $(2^2,2^2,2^2)$, $(2^1,2^1,2^4)$, y $(1,1,2^6)$. Hay $2$ posibilidades de los poderes de la $3$$5$. Por lo $|X^{(1\;2)}| = 16$.
• Del mismo modo, $|X^{(1\;3)}|=|X^{(2\;3)}|=16$.
• $X^{(1\;2\;3)}$, el conjunto de los elementos fijados por la $3$ciclo $(1\;2\;3)$. Esto significa $x=y=z$ en el triple $(x,y,z)$, por lo que sólo hay un elemento en común: $(60,60,60)$. Por lo $|X^{(1\;2\;3)}| = 1$.
• Del mismo modo, $|X^{(1\;3\;2)}| = 1$.

Así que por Burnside del lema, $$ |X/G| = \frac{2800 + 16 + 16 + 16 + 1 + 1}{6} = 475. $$

Este enfoque es fácil de generalizar a contar factorizations de $xyz=n$. Se generaliza a la factorización con más factores, pero, a continuación, el grupo de acción es más complicado, así que hay más de los casos a tratar, y son individualmente más difícil de contar.