Esta es una aplicación directa de la Enumeración de Polya
Teorema. Supongamos $Z(S_n)$ es el ciclo del índice del grupo simétrico
dada por la recurrencia por Lovasz 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.$$
Obtenemos por la MASCOTA de la siguiente fórmula para la OGF de multisets (de
los productos) en $n$ ranuras (los clientes)
$$Z(S_n)\left(\sum_{k=1}^m X_k\right).$$
Nota sin embargo de que tenemos una restricción en estos multisets que es
que hay en la mayoría de las $q_k$ productos de tipo $k.$ Ahora la generación de
la función
$$\prod_{k=1}^m \frac{1}{1-X_k}
Z(S_n)\left(\sum_{k=1}^m X_k\right)$$
tiene la propiedad de que el coeficiente de $X_k^q$ cuenta con multisets
en la mayoría de las $q$ instancias de producto $k$ (frente a exactamente
$q$). Por lo tanto, el resultado final es (aquí el corchete indica
coeficiente de extracción)
$$\left[\prod_{k=1}^m X_k^{q_k}\right]
\prod_{k=1}^m \frac{1}{1-X_k}
Z(S_n)\left(\sum_{k=1}^m X_k\right).$$
El siguiente código implementa esta usando la fórmula de Arce. La fórmula
puede ser optimizado para valores particulares de las cantidades $q_k$ en
diversas maneras, por ejemplo, por
$$\text{sustitución de}\quad 1/(1-X_k) \quad\text{por}\quad
1+X_k+\cdots+X_k^{q_k}.$$
(De hecho numérico experimentos indican que esto no es siempre una
la mejora.)
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;
pet_cycleind_symm :=
proc(n)
local p, s;
opción de recordar;
si n=0 entonces devolver 1; fi;
ampliar(1/n*añadir(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
V :=
proc(q, n)
local gf, m, vp;
m := nops(q);
gf := mul(1/(1-X[k]), k=1..m)*
pet_varinto_cind(añadir(X[k], k=1..m),
pet_cycleind_symm(n));
para vp para hacer m
gf := coeftayl(gf, X[vp]=0, q[vp]);
od;
gf;
end;
W := n -> V([seq(n, q=1..n)], n);
Una sesión con este código se parece a esto:
> V([3,3,3,3], 5);
40
> V([3,3,3,4], 5);
43
> V([5,5,5,5], 5);
56
y tenemos la confirmación de los valores dados por el OP.
Verificación adicional puede ser obtenida por el tratamiento de la especial
caso de $n$ productos con capacidad max $q_k = n$ $n$ clientes.
Aquí no necesitamos el factor de en frente que hemos añadido debido a que la
ciclo del índice en sí aplica el límite de $n$ de los productos de cada tipo. Nosotros
así se obtiene la fórmula (cuyas diferentes multinomials contribuir
una el total):
$$\left. Z(S_n)\left(\sum_{k=1}^m X_k\right)\right|_{X_k=1}$$
Ahora recuerdo la OGF del conjunto múltiple operador $\mathfrak{M}_{=n}$ que
es
$A$Z(S_n) = [z^n]
\exp\left(a_1 z + a_2 \frac{z^2}{2}
+ a_3 \frac{z^3}{3}
+ a_4 \frac{z^4}{4}
+\cdots \right).$$
En sustitución de en el ciclo del índice que poner
$$a_p = \left. \sum_{k=1}^m X_k^p\right|_{X_k=1} = n$$
porque tenemos $m=n$ en este caso especial.
Esto da lugar a la fórmula
$$[z^n] \exp\left(n z n + \frac{z^2}{2}
n + \frac{z^3}{3}
n + \frac{z^4}{4}
+\cdots \right)
= [z^n] \exp\left(n\log\frac{1}{1-z}\right)
\\ = [z^n] \frac{1}{(1-z)^n}
= {2n-1\elegir n-1}.$$
Y, de hecho, cuando se ejecute la de Arce código obtenemos
> seq(W(n), n=1..18);
1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078,
5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650
> seq(binomial(2*n-1,n-1), n=1..18);
1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078,
5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650
Esta secuencia es OEIS A001700.
El mismo cálculo funciona cuando todas las cantidades $q_k$ de la $m$
los productos son, al menos, $n$ donde se obtiene el coeficiente binomial
$${n+m-1\choose m-1}$ $ , que parece ser una aplicación de estrellas y barras.
Observación. La principal fórmula de arriba representa correctamente la
combinatoria givens de este problema, pero a diferencia de en el ejemplo que acabo de
presentado con $n$ productos $n$ de los clientes y la capacidad de $n$ dijo
fórmula calcula todos los posibles multisets y por lo tanto no produce una
la reducción en la complejidad del problema.
Adenda. No necesitamos el Polya Enumeración Teorema de aquí. Voy a
dejo el anterior para los curiosos para consultar. La fórmula es, por supuesto,
$$[z^n] \prod_{k=1}^m (1+z+z^2+\cdots+z^{q_k}).$$
Esto produce que el uniforme de la capacidad de $q$
$$[z^n] \prod_{k=1}^m \frac{1-z^{q+1}}{1-z}
= [z^n] \frac{(1-z^{q+1})^m}{(1-z)^m}
\\ = \sum_{p=0}^{\lfloor n/(q+1)\rfloor}
{m\elegir p} (-1)^p {m-1+n-p(p+1)\elegir m-1}.$$
Al $q\ge n$ sólo el término para $p=0$ contribuye y obtenemos el mismo
la fórmula de la MASCOTA de la computación.
