suma de todos los términos en submultisets de A000707

Question

Consideremos el multiconjunto 1,2,2,3,3,3, y A000707. ¿Cuál es la suma de todos los términos de los subconjuntos no ordenados y de los subconjuntos ordenados a medida que se avanza en la secuencia? . Para k=1 a 4 la secuencia comienza por los submultisets no ordenados 1,7,42,234 y la suma de los términos de todos los submultisets ordenados es 1,10,126,1904. https://oeis.org/A000707

Answer 1

Trabajando con la misma notación que en este MSE post que tenemos para el caso de los multiconjuntos ordenados la especie etiquetada para $n$ fijo

$$\mathfrak{P_{\le 1}}(\mathcal{U}\mathcal{Z}) \mathfrak{P_{\le 2}}(\mathcal{U}^2\mathcal{Z}) \mathfrak{P_{\le 3}}(\mathcal{U}^3\mathcal{Z}) \cdots \mathfrak{P_{\le n}}(\mathcal{U}^n\mathcal{Z}).$$

Esto representa una fila de $m$ franjas horarias ordenadas disponibles en las que seleccionamos como máximo uno para contener el valor uno, como máximo dos para contener el valor dos, a lo sumo tres para contener el valor tres y así sucesivamente y las ranuras por valor forman un conjunto. Se obtiene la función generadora exponencial

$$G(z) = \left.\frac{\partial}{\partial u} \prod_{q=1}^n \left(\sum_{p=0}^q \frac{u^{qp} z^p}{p!}\right) \right|_{u=1} \\ = \left. \prod_{q=1}^n \left(\sum_{p=0}^q \frac{u^{qp} z^p}{p!}\right) \sum_{q=1}^n \left(\sum_{p=0}^q \frac{u^{qp} z^p}{p!}\right)^{-1} \left(\sum_{p=0}^q \frac{qp u^{qp-1} z^p}{p!}\right) \right|_{u=1} \\ = \prod_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right) \sum_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right)^{-1} \left(\sum_{p=0}^q \frac{qp z^p}{p!}\right) \\ = \prod_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right) \sum_{q=1}^n q\times \left(\sum_{p=0}^q \frac{z^p}{p!}\right)^{-1} \left(\sum_{p=1}^q \frac{z^p}{(p-1)!}\right) \\ = \prod_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right) \sum_{q=1}^n q\times \left(\sum_{p=0}^q \frac{z^p}{p!}\right)^{-1} \left(- \frac{z^{q+1}}{q!} + z \sum_{p=0}^{q} \frac{z^p}{p!}\right) \\ = \prod_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right) \sum_{q=1}^n q\times \left(z - \frac{z^{q+1}}{q!} \left(\sum_{p=0}^q \frac{z^p}{p!}\right)^{-1}\right) \\ = z \prod_{q=1}^n \left(\sum_{p=0}^q \frac{z^p}{p!}\right) \sum_{q=1}^n q\times \left(1 - \frac{z^{q}}{q!} \left(\sum_{p=0}^q \frac{z^p}{p!}\right)^{-1}\right).$$

Estamos interesados en $n! [z^n] G(z)$ que da lugar a la secuencia

$$1, 10, 126, 1928, 34630, 713982, 16627912, 431880584, \\ 12380457636, 388321923170,\ldots$$

que al parecer aún no tiene entrada en la OEIS.

Una implementación es así (aviso, enumeración total, no optimizada, probada para valores hasta doce)

X :=
proc(n)
option remember;
local gf, res, term, pos;

    if n=1 then return 1 fi;

    gf := expand(add(A\[q\], q=1..n)^n);

    res := 0;

    for term in gf do
        for pos to n do
            if degree(term, A\[pos\]) > pos then
                break;
            fi;
        od;

        if pos = n+1 then
            res := res +
            lcoeff(term)\*add(q\*degree(term, A\[q\]), q=1..n);
        fi;
    od;

    res;
end;

Z :=
proc(n)
option remember;
local gf;

    gf := z\*mul(add(z^p/p!, p=0..q), q=1..n)
    \* add(q\*(1-z^q/q!/add(z^p/p!, p=0..q)), q=1..n);

    n!\*coeff(factor(gf), z, n);
end;