Sacando bolas de una urna o contando ciertos posets.

Question

Un colega mío, tenía curiosidad sobre el número de posible inicio-configuraciones en un juego. El juego en sí no es conocido para mí, pero la pregunta que se formuló como urna problema era interesante.

Urna problema:

• Supongamos que tenemos una urna que contiene 100 bolas. Las bolas son de color, 25 son de color rojo, 25 azul, verde 25 y 25 son de color negro. Elegimos cuatro bolas sin reemplazo y repita este paso hasta que la urna está vacía.

• Nosotros a fin de obtener el 25 grupos de cuatro bolas de cada uno y la pregunta es: ¿cuántas de las configuraciones de este tipo son posibles? Con lo que podemos suponer que el orden de las $4$ bolas en cada grupo no es relevante, así como el orden de la $25$ grupos no es relevante.

Una reformulación:

• Dado un alfabeto $V=\{1,2,3,4\}$ consideramos $4$letra $x_1x_2x_3x_4$ con $1\leq x_1\leq x_2\leq x_3\leq x_4\leq 4$ cuando se la considera como números.

• Estos $4$-de la carta de las palabras son los bloques de construcción de palabras de longitud $100$. Tomamos $25$ bloques de este tipo para formar una $100$letras de la palabra $w=b_1b_2\ldots b_{25}$ con la propiedad de que $b_j\leq b_{j+1}, 1\leq j\leq 25$ cuando se la considera como números.

Pregunta: ¿cuántas palabras de este tipo contienen exactamente $25$ caracteres de cada uno de los caracteres $j\in V, 1\leq j\leq 4$.

En general nos da un alfabeto $V=\{1,2,\ldots,q\}$ con un tamaño de $|V|=q$.

• (a) consideramos las palabras de longitud $N$ y bloques de construcción $x_1x_2\ldots x_M$ de tamaño de $M$ con $1\leq x_1\leq x_2\leq \cdots \leq x_M\leq q$ e $M|N$, es decir, $N$ ser un múltiplo entero de $N$.

• (b) Las palabras son de la forma $w=b_1b_2\ldots b_{N/M}$ con $b_j\leq b_{j+1}, 1\leq j \leq N/M-1$.

• (c) Estamos buscando el número de $\color{blue}{A_q(N,M)}$, el número de palabras tal como se especifica en (a) y (b) que contengan $N/q$ caracteres de cada uno de los caracteres $j\in V, 1\leq j\leq q$ lo que implica que $N$ es un múltiplo entero de $q$ así.

En este marco, la urna problema está pidiendo $\color{blue}{A_4(100,4)}$.

El número de bloques de construcción de la $A_q(N,M)$ puede ser fácilmente determinado. Es \begin{align*} \sum_{1\leq x_1\leq x_2\leq\cdots\leq x_M\leq q}1=\binom{M+q-1}{M}\tag{1} \end{align*}

Una generación de la función de (1) puede ser fácilmente derivados. Tenemos \begin{align*} \sum_{M=0}^\infty\sum_{q=0}^\infty x^My^q\binom{M+q-1}{M}&=\frac{1-x}{1-x-y}\\ &=1+y\left(1+x+x^2+x^3+x^4+\cdots\right)\\ &\qquad+y^2\left(1+2x+3x^2+4x^3+5x^4+\cdots\right)\\ &\qquad+y^3\left(1+3x+6x^2+10x^3+\color{blue}{15}x^4+\cdots\right)\\ &\qquad\cdots \end{align*} Denotando con $[x^M]$ el coeficiente de $x^M$ en una serie vamos a ver, por ejemplo $[x^4y^3]\frac{1-x}{1-x-y}=\binom{6}{2}=15$ que es el número de bloques de construcción de tamaño $4$ cuando se administra una de tres letras del alfabeto $V=\{1,2,3\}$. Estos $15$ bloques de construcción son \begin{align*} 1111\quad1122\quad1222\quad1333\quad2233\\ 1112\quad1123\quad1223\quad2222\quad2333\\ 1113\quad1133\quad1233\quad2223\quad3333\\ \end{align*}

La parte difícil (al menos para mí) es determinar el número de palabras válidas $A_q(N,M)$ , que puede ser generado a partir de estos bloques de construcción. He tratado de derivar una generación de la función que describe este escenario, pero no me exitosa hasta ahora.

Posets: Otro enfoque podría ser el uso de posets basado en el enfoque:

• Empezar con una palabra vacía y anexar $N/M$ veces un bloque de construcción respetando el orden dado en (b).

• Derivar una generación de función para el número de posets.

Para ver mejor la situación, aquí es un manejable ejemplo. Estamos buscando a$A_2(12,M)$ el número de palabras de longitud $12$ a partir de dos letras del alfabeto con diferentes bloques de tamaños de $M$ siguiente (a) - (c) de arriba. El Hasse-diagramas de $M=2,3,4,6$ son:

Vemos gradual posets de longitud $N/M$ con $A_2(12,2)=A_2(12,6)=4$ e $A_2(12,3)=A_2(12,4)=5$ lo que indica la simetría \begin{align*} A_q(N,M)=A_q(N,N/M) \end{align*}

Aquí está una lista de valores pequeños de a$A_2(N,M)$: $$ \begin{array}{r|rrrrrr} M&1&2\\ A_2(2,M)&1&1\\ \hline M&1&2&4\\ A_2(4,M)&1&2&1\\ \hline M&1&2&3&6\\ A_2(6,M)&1&2&2&1\\ \hline M&1&2&4&8\\ A_2(8,M)&1&3&3&1\\ \hline M&1&2&5&10\\ A_2(10,M)&1&3&3&1\\ \hline M&1&2&3&4&6&12\\ A_2(12,M)&1&4&5&5&4&1\\ \end{array} $$

Resumen: La cuestión es cómo encontrar una fórmula para $A_q(N,M)$ o cómo derivar una función de la generación de estos números. Alternativamente, hay una técnica apropiada para contar el número de posets correspondiente a $A_q(N,M)$?

Answer 1

Parece que estas son multisets de multisets que puede ser enumeran utilizando el Polya Enumeración Teorema (PET), mismo que fue publicado en la siguiente MSE enlace.

La respuesta es un caso especial de lo que se presentó allí y se da por

$$\left[\prod_{k=1}^q A_k^{N/p}\right] Z\left(S_{N/M}; Z\left(S_M; \sum_{k=1}^q A_{k}\right)\right).$$

En términos de la combinatoria de las clases que hemos hecho uso de la etiqueta clase

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{MSET}_{=N/M} \left(\textsc{MSET}_{=M} \left(\sum_{k=1}^q \mathcal{A}_{k}\right)\right).$$

El post vinculado documentos cómo calcular el ciclo de índice de la grupo simétrico y cómo sustituir los $Z(S_M)$ a $Z(S_{N/M}).$

La pregunta es, ¿por qué podemos usar multisets aquí? La respuesta es que hay un uno-a-uno el mapeo entre los multisets y lo OP las llamadas de bloques de construcción. Cada bloque corresponde obviamente a exactamente un conjunto múltiple y cada conjunto múltiple a una cuadra, a saber, por orden de su los mandantes. Lo mismo sucede con multisets de bloques.

Esto se ha implementado en madera de Arce y aquí están algunos ejemplos de los resultados que una potencial contribuyente puede comparar a su trabajo y / o utilizar para comprobar que tenemos la correcta comprensión del problema.

> seq(Un(2,12), M), M en divisores(12));
 1, 4, 5, 5, 4, 1

> seq(Un(3,12), M), M en divisores(12));
 1, 15, 25, 23, 10, 1

> seq(Un(4,12), M), M en divisores(12));
 1, 47, 93, 70, 22, 1

> seq(Un(4,20), M), M en divisores(20));
 1, 306, 2505, 1746, 73, 1

> seq(Un(5,20), M), M en divisores(20));
 1, 2021, 19834, 11131, 191, 1

El Arce código para el de arriba va como sigue. El lector es invitado a presente sus resultados en un idioma de su elección para una de Rosetta piedra efecto.

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, subsl, polyvars, indvars, v, bote;

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

 subsl := [];

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

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

 subsl := [op(subsl), v=subs(subs1, poli)];
od;

 subs(subsl, ind);
end;

pet_cycleind_comp :=
proc(idxtrg, idx)
local varstrg, vars, vt, sbstrg, sbs, len;

 varstrg := indets(idxtrg);
 var := indets(idx);

 sbstrg := [];

 para vt en varstrg ¿
 len := op(1, vt);

 sbs :=
 [seq(v = a[op(1, v)*len], v en vars)];

 sbstrg :=
[op(sbstrg),
 [len] = subs(sbs, idx)];
od;

 expanda(subs(sbstrg, idxtrg));
end;

A :=
proc(q, N, M)
opción de recordar;
local cind_block, cind_word, cind_comp,
 vars, gf, vidx;

 si N mod p > 0 o N mod M > 0, entonces
 volver a FALLAR;
fi;

 cind_block := pet_cycleind_symm(M);
 cind_word := pet_cycleind_symm(N/M);

 cind_comp := pet_cycleind_comp(cind_word, cind_block);

 var := suma ([p], p=1..p);
 gf := expand(pet_varinto_cind(vars, cind_comp));

 por vidx para q hacer
 gf := coef(gf, [vidx], N/p);
od;

gf;
end;

Adenda. Con la respuesta anterior, podemos calcular el compuesto ciclo índice del operador

$$\textsc{MSET}_{=N/M}(\textsc{MSET}_{=M}(\cdot))$$

y, a continuación, sustituir las variables en este ciclo de índice. M. Scheuer en su respuesta sugiere un enfoque diferente, donde se sustituye la las variables en el primer ciclo de índice, la obtención de la multisets, y luego sustituye en $Z_{N/M}.$ datos Experimentales indican que este el enfoque es superior. El mismo efecto puede lograrse mediante la expansión el compuesto ciclo de índice en sus constituyentes. Esto produce que el siguiente Arce código (código duplicado omitido).

pet_cycleind_comp :=
proc(idxtrg, idx)
local varstrg, vars, vt, sbstrg, sbs, len;

 varstrg := indets(idxtrg);
 var := indets(idx);

 sbstrg := [];

 para vt en varstrg ¿
 len := op(1, vt);

 sbs :=
 [seq(v = a[op(1, v)*len], v en vars)];

 sbstrg :=
[op(sbstrg),
 [len] = subs(sbs, idx)];
od;

 subs(sbstrg, idxtrg);
end;


A :=
proc(q, N, M)
opción de recordar;
local cind_block, cind_word, cind_comp,
 vars, gf, vidx;

 si N mod p > 0 o N mod M > 0, entonces
 volver a FALLAR;
fi;

 cind_block := pet_cycleind_symm(M);
 cind_word := pet_cycleind_symm(N/M);

 cind_comp := pet_cycleind_comp(cind_word, cind_block);

 var := suma ([p], p=1..p);
 gf := expand(pet_varinto_cind(vars, cind_comp));

 por vidx para q hacer
 gf := coef(gf, [vidx], N/p);
od;

gf;
end;

AX :=
proc(q, N, M)
opción de recordar;
local cind_block, cind_word, cind_comp,
 vars, bloques, gf, vidx;

 si N mod p > 0 o N mod M > 0, entonces
 volver a FALLAR;
fi;

 cind_block := pet_cycleind_symm(M);
 var := suma ([p], p=1..p);
 bloques := pet_varinto_cind(vars, cind_block);

 cind_word := pet_cycleind_symm(N/M);
 gf := expand(pet_varinto_cind(bloques, cind_word));

 por vidx para q hacer
 gf := coef(gf, [vidx], N/p);
od;

gf;
end;

Answer 2

Esta respuesta es un suplemento a la gran respuesta de @MarkoRiedel y una especie de reflexión para ver mejor los mecanismos de trabajo. El problema original fue determinar $A_4(100,4)$ que puede ser escrito de acuerdo a Markos respuesta \begin{align*} A_4(100,4)=[a^{25}b^{25}c^{25}d^{25}]Z\left(S_{25}(Z\left(S_4;a+b+c+d\right)\right) \end{align*} Es una tarea imposible abordar este problema de forma manual. Pero podemos ver todos los aspectos importantes por tomar un parámetro más pequeño $N=8$ en lugar de $N=100$. Dejando el otro parámetro de $M=4,q=4$ sin cambios tenemos $N/M=N/q=2$ y calculamos \begin{align*} \color{blue}{A_2(8,4)=[a^{2}b^{2}c^{2}d^{2}]Z\left(S_{2}(Z\left(S_4;a+b+c+d\right)\right)}\tag{1} \end{align*}

Cálculo de $Z(S_4)$:

Comenzamos calculando $Z(S_4)$ mediante el uso de la relación de recurrencia: \begin{align*} Z(S_n)=\frac{1}{n}\sum_{j=1}^n a_j Z(S_{n-j})\qquad\textrm{where}\qquad Z(S_0)=1 \end{align*} Obtenemos \begin{align*} Z(S_0)&=1\\ Z(S_1)&=\frac{1}{1}\sum_{j=1}^1a_jZ(S_{1-j})=a_1Z(S_0)\\ &=a_1\\ Z(S_2)&=\frac{1}{2}\sum_{j=1}^2 a_jZ(S_{2-j})=\frac{1}{2}\left(a_1Z(S_1)+a_2Z(S_0)\right)\\ &=\frac{1}{2}\left(a_1^2+a_2\right)\tag{2}\\ Z(S_3)&=\frac{1}{3}\sum_{j=1}^3 a_jZ(S_{3-j})=\frac{1}{3}\left(a_1\frac{1}{2}\left(a_1^2+a^2\right)+a_2a_1+a_3\right)\\ &=\frac{1}{6}\left(a_1^3+3a_1a_2+2a_3\right)\\ \color{blue}{Z(S_4)}&=\frac{1}{4}\sum_{j=1}^4a_jZ(S_{4-j})\\ &=\frac{1}{4}\left(a_1\frac{1}{6}\left(a_1^3+3a_1a_2+2a_3\right)+a_2\frac{1}{2}\left(a_1^2+a_2\right)+a_3a_1+a_4\right)\\ &\,\,\color{blue}{=\frac{1}{24}\left(a_1^4+6a_1^2a_2+8a_1a_3+3a_2^2+6a_4\right)}\tag{3} \end{align*}

Ordinaria de la generación de la función del ciclo del índice de $Z(S(n))$ es \begin{align*} \sum_{n=0}^\infty Z(S_n)) z^n=\exp\left(a_1z+\frac{a_2}{2}z^2+\frac{a_3}{3}z^3+\cdots\right) \end{align*} Podemos utilizar esta función para realizar una comprobación de (3) a través de Wolfram Alpha escribiendo

SeriesCoefficient[Exp[a_1*z+a_2*z^2/2+a_3*z^3/3+a_4*z^4/4],{z,0,4}]

lo que da el resultado esperado.

Cálculo de $Z(S_4;a+b+c+d)$

Sustituimos $a+b+c+d$ (2)

\begin{align*} Z(S_4)=\frac{1}{24}\left(a_1^4+6a_1^2a_2+8a_1a_3+3a_2^2+6a_4\right) \end{align*}

mediante la sustitución de $a_j$ con $a^j+b^j+c^j+d^j$ y obtener \begin{align*} \color{blue}{Z(S_4;}&\color{blue}{a+b+c+d)}\\ &=\frac{1}{24}\left((a+b+c+d)^4+6(a+b+c+d)^2(a^2+b^2+c^2+d^2)\right.\\ &\qquad\qquad \left.+8(a+b+c+d)(a^3+b^3+c^3+d^3)\right.\\ &\qquad\qquad \left.+3(a^2+b^2+c^2+d^2)^2+6(a^4+b^4+c^4+d^4)\right)\\ &=\cdots\\ &\,\,\color{blue}{=a^4+a^3b+a^3c+a^3d+a^2b^2+a^2bc+a^2bd+a^2c^2+a^2cd+a^2d^2}\\ &\qquad\color{blue}{+ab^3+ab^2c+ab^2d+abc^2+abcd+abd^2+ac^3+ac^2d+acd^2+ad^3}\\ &\qquad\color{blue}{+b^4+b^3c+b^3d+b^2c^2+b^2cd+b^2d^2+bc^3+bc^2d+bcd^2+bd^3}\\ &\qquad\color{blue}{+c^4+c^3d+c^2d^2+cd^3+d^4}\tag{4} \end{align*}

Tenga en cuenta que (4) $35$ sumandos, cada uno con coeficiente de $1$, por lo que $Z(S_4;a+b+c+d)|_{a=b=c=d=1}=35$. Esto corresponde a (1) en el post original que es, desde el $M=4$ e $q=4$ \begin{align*} \sum_{1\leq x_1\leq x_2\leq x_3 \leq x_4\leq 4}1=\binom{4+4-1}{4}=\binom{7}{3}=35 \end{align*}

Cálculo de $[a^2b^2c^2d^2]Z(S_2;Z(S_4;a+b+c+d))$:

Sustituimos (4) en $Z(S_2)=\frac{1}{2}\left(a_1^2+a_2\right)$ según (2) y obtenemos \begin{align*} \color{blue}{[a^2}&\color{blue}{b^2c^2d^2]Z(S_2;Z(S_4;a+b+c+d))}\\ &=[a^2b^2c^2d^2]\frac{1}{2}\left(a^4+a^3b+a^3c+a^3d+a^2b^2+a^2bc+a^2bd\right.\\ &\qquad\qquad\qquad\quad\left.+a^2c^2+a^2cd+a^2d^2+ab^3+ab^2c+ab^2d\right.\\ &\qquad\qquad\qquad\quad\left.+abc^2+abcd+abd^2+ac^3+ac^2d+acd^2\right.\\ &\qquad\qquad\qquad\quad\left.+ad^3+b^4+b^3c+b^3d+b^2c^2+b^2cd +b^2d^2 \right.\\ &\qquad\qquad\qquad\quad\left.+bc^3+bc^2d+bcd^2+bd^3+c^4+c^3d+c^2d^2\right.\\ &\qquad\qquad\qquad\quad\left.+cd^3+d^4\right)^2\\ &\quad+[a^2b^2c^2d^2]\frac{1}{2}\left(a^8+a^6b^2+a^6c^2+a^6d^2+a^4b^4+a^4b^2c^2+a^4b^2d^2\right.\\ &\quad\qquad\qquad\qquad\quad\left.+a^4c^4+a^4c^2d^2+a^4d^4 +a^2b^6+a^2b^4c^2+a^2b^4d^2\right.\\ &\quad\qquad\qquad\qquad\quad\left.+a^2b^2c^4+(abcd)^2+a^2b^2d^4+a^2c^6 +a^2c^4d^2+a^2c^2d^4 \right.\\ &\quad\qquad\qquad\qquad\quad\left.+a^2d^6+b^8+b^6c^2+b^6d^2+b^4c^4+b^4c^2d^2+b^4d^4\right.\\ &\quad\qquad\qquad\qquad\quad\left.+b^2c^6+b^2c^4d^2+b^2c^2d^4+b^2d^6 +c^8+c^6d^2+c^4d^4\right.\\ &\quad\qquad\qquad\qquad\quad\left.+c^2d^6+d^8\right)\\ &=[a^2b^2c^2d^2]\frac{1}{2}\left(a^2b^2+a^2bc+a^2bd+a^2c^2+a^2cd+a^2d^2\right.\\ &\qquad\qquad\qquad\quad\left.+ab^2c+ab^2d+abc^2+abcd+abd^2+ac^2d+acd^2\right.\\ &\qquad\qquad\qquad\quad\left.+b^2c^2+b^2cd+b^2d^2+bc^2d+bcd^2+c^2d^2\right)^2\\ &\quad+[a^2b^2c^2d^2]\frac{1}{2}(abcd)^2\tag{5}\\ &=[a^2b^2c^2d^2]\frac{1}{2}\left(2\left(a^2b^2\right)\left(c^2d^2\right) +2\left(a^2bc\right)\left(bcd^2\right) +2\left(a^2bd\right)\left(bc^2d\right)\right.\\ &\qquad\qquad\qquad\quad\left.+2\left(a^2c^2\right)\left(b^2d^2\right) +2\left(a^2cd\right)\left(b^2cd\right) +2\left(a^2d^2\right)\left(b^2c^2\right)\right.\\ &\qquad\qquad\qquad\quad\left.+2\left(ab^2c\right)\left(acd^2\right) +2\left(ab^2d\right)\left(ac^2d\right) +2\left(abc^2\right)\left(abd^2\right)\right.\\ &\qquad\qquad\qquad\quad\left.+(abcd)^2\right)\\ &\quad+[a^2b^2c^2d^2]\frac{1}{2}(abcd)^2\tag{6}\\ &\,\,\color{blue}{=10}\tag{7} \end{align*}

Comentario:

• En (5) mantenemos los términos de la línea de arriba que han lineal o cuadrado factores, ya que los otros términos no contribuyen a $[a^2b^2c^2d^2]$.

• En (6) se multiplica y indicar los factores por mantenerlos en el paréntesis.

Finalmente, conseguimos el resultado (7): \begin{align*} \color{blue}{A_4(8,4)}&=[a^2b^2c^2d^2]Z(S_2;Z(S_4;a+b+c+d))\\ &\,\,\color{blue}{=10} \end{align*}

Podemos comprobar el resultado mediante un listado de las $35$ configuraciones válidas de acuerdo a $Z(S_4;a+b+c+d)$ $$ \begin{array}{cccc} 1111&1222&2222&3333\\ 1112&\color{blue}{1223}&2223&3334\\ 1113&\color{blue}{1224}&2224&\color{blue}{3344}\\ 1114&\color{blue}{1233}&\color{blue}{2233}&3444\\ \color{blue}{1122}&\color{blue}{1234}&\color{blue}{2234}&4444\\ \color{blue}{1123}&\color{blue}{1244}&\color{blue}{2244}&\\ \color{blue}{1124}&1333&2333&\\ \color{blue}{1133}&\color{blue}{1334}&\color{blue}{2334}&\\ \color{blue}{1134}&\color{blue}{1344}&\color{blue}{2344}&\\ \color{blue}{1144}&1444&2444&\\ \end{array} $$

Las cadenas válidas que no tienen más de dos repeticiones de cada uno de los personajes están marcados $\mathrm{\color{blue}{blue}}$. Correspondiente con $[a^2b^2c^2d^2]Z(S_2(Z(S_4;a+b+c+d))$ nos concatenar la validez $\mathrm{\color{blue}{blue}}$ cadenas y encontrar el $10$ resultante cadenas \begin{align*} 1122.3344\qquad1144.2233\\ 1123.2344\qquad1223.1344\\ 1124.2334\qquad1224.1334\\ 1133.2244\qquad1233.1244\\ 1134.2234\qquad1234.1234\\ \end{align*}