Cuántas formas de escribir un número $n$ como el producto de números naturales $\geq 2$ ?

Question

Estoy buscando una forma cerrada (o un algoritmo eficiente) para $f(n)$ el número de formas en que $n$ puede escribirse como un producto de números naturales $\geq 2$ . Tenga en cuenta que $f(n)=\sum_{i=1}^{\Omega(n)}{g(n,i)}$ , donde $g(n,i)$ es el número de formas en que $n$ puede escribirse como un producto de $i$ números naturales $\geq 2$ y $\Omega(n)$ es el número total de factores primos de $n$ . Si es útil, podemos suponer que se nos da la factorización prima de $n$ .

Por ejemplo, si $n=40$ entonces tenemos lo siguiente:

$\Omega(40)=\Omega(2^35^1)=3+1=4$

$g(40,1)=1: (40)$

$g(40,2)=3: (20, 2), (10, 4), (8, 5)$

$g(40,3)=2: (10, 2, 2), (5, 4, 2)$

$g(40,4)=1: (5, 2, 2, 2)$

así que $f(40)=7$

Partición (teoría de los números) - Tamaño de la pieza o número de piezas restringido tiene resultados potencialmente útiles. Es fácil conseguir $g(n,2)$ , ya que es sólo $\frac{d(n)-2}{2}$ , donde $d(n)$ es el número de divisores de $n$ .

Answer 1

Entre varios enfoques posibles, podemos considerar este problema como una aplicación directa del Teorema de Enumeración de Polya y muy similar al problema discutido en este MSE enlace .

Recordemos la recurrencia de Lovasz para el índice de ciclo $Z(S_n)$ de el operador de conjuntos múltiples $\mathfrak{M}_{=n}$ en $n$ ranuras, que es $$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

Supongamos que la factorización primaria de $n$ viene dada por $$n=\prod_p p^v.$$

Aplicando el PET se deduce ahora casi por inspección que el deseado de particiones multiplicativas en $k$ viene dada por el término $$F(n, k) = \left[\prod_p X_p^v\right] Z(S_k)\left(-1 + \prod_p \frac{1}{1-X_p}\right)$$ donde el corchete denota la extracción de coeficientes de las series de potencia formales.

Estamos interesados en $$G(n) = \sum_{k=1}^{\Omega(n)} F(n, k).$$

Ahora recordemos la función generadora del índice de ciclo del grupo simétrico que es $$H(z) = \sum_{q\ge 0} Z(S_q) z^q = \exp\left(a_1z + a_2\frac{z^2}{2} + a_3\frac{z^3}{3}+\cdots\right) = \exp\left(\sum_{l\ge 1} a_l \frac{z^l}{l}\right).$$

Esto da para $G(n)$ $$G(n) = \left[\prod_p X_p^v\right] \exp\left(\sum_{l\ge 1} \frac{1}{l} \left(-1 + \prod_p \frac{1}{1-X_p^l}\right)\right).$$

Recordando $v_p(n)$ que es el exponente de la máxima potencia de $p$ que divide $n$ finalmente obtenemos

$$G(n) = \left[\prod_p X_p^v\right] \exp\left(\sum_{l=1}^{\max_p v_p(n)} \frac{1}{l} \left(-1 + \prod_p \frac{1}{1-X_p^l}\right)\right).$$

Esta fórmula tiene un cierto valor estético. Implementada en Maple producirá producirá la siguiente secuencia: $$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, 7, 2, 2, 2, 9, 1, 2, 2, 7, \\ 1, 5, 1, 4, 4, 2, 1, 12, \ldots$$

que nos señala OEIS A001055 donde información adicional, incluyendo recurrencias simples para cálculo práctico de esta función.

El código de Maple para la fórmula anterior es el siguiente (aquí hemos sustituido el índice del número primo en la variable $X$ por un índice posicional en la variable $Y$ ):

with(numtheory);

facts :=
proc(n)
    option remember;
    local f, gf, p, res;

    f := op(2, ifactors(n));
    gf := exp(add(1/l\*
                  (-1+mul(1/(1-Y\[p\]^l), p=1..nops(f))),
                  l=1..max(map(p->p\[2\], f))));

    res := gf;
    for p to nops(f) do
        res := coeftayl(res, Y\[p\]=0, f\[p\]\[2\]);
    od;

    res;
end;