17 votos

Número de factorizations de distintos factores

Deje $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ un entero con $p_i$ el primer y el $e_i \in \mathbb N$. La factorización en primos supone para ser conocido, es decir, ya sabemos $p_1, \dotsc, p_k$$e_1, \dotsc e_k$.

Es posible encontrar el número de factorizations de longitud $m$ de la forma

$n = n_1 \cdot n_2 \dotsm n_m$ tal que $n_1 < n_2 < \dotsb < n_m$ otros de fuerza bruta?

(Que significa dos factorizations que son sólo un reordenamiento de cada uno de los otros son considerados como la misma, por ejemplo, $1 \times 2 \times 3$ se considera el mismo como $1 \times 3 \times 2$, por lo que solo se tiene en cuenta aquellos en orden ascendente).

Ejemplo: Para el número de $n = 12 = 2^2 \cdot 3$ tenemos las siguientes factorizations con los factores en orden ascendente:

Para $m=1$ tenemos una:

  • $12$

Para $m=2$ tenemos tres:

  • $1 \times 12$
  • $2 \times 6$
  • $3 \times 4$

Para $m=3$ tenemos dos:

  • $1 \times 2 \times 6$
  • $1 \times 3 \times 4$

5voto

martin Puntos 4627

Casos especiales

Para $n = p_i p_2 \cdots p_k$, (todos con exponente $1$), la multiplicación de las particiones $m_1, m_2,\dots, m_{k+1}$ son dados por los coeficientes de la expansión de la serie $$f(x,k)=\dfrac{1-(k-1) x}{\prod _{n=1}^k (1-n x)}$$ where the $m$th partition of $p_1 p_2 \cdots p_k$ is give by the $(k-m+2)$th coeficiente.

f[k_] := (1 - (k - 1) x)/Product[1 - n x, {n, 1, k}]
g[a_, b_] := CoefficientList[Series[f@b, {x, 0, b + a}], x][[a - b + 2]]
h[n_] := g[n, #] & /@ Range[n + 1]

h[#] & /@ Range@6

da

\begin{array}{c} 1 & 1\\ 1 & 2 & 1\\ 1 & 4 & 4 & 1\\ 1 & 8 & 13 & 7 & 1\\ 1 & 16 & 40 & 35 & 11 & 1\\ 1 & 32 & 121 & 155 & 80 & 16 & 1\\ \end{array}

por ejemplo $30$ tiene particiones de longitud $m_1=1,\ m_2=4,\ m_3=4,\ m_4=1$:

$m_1=1$:

  • $30$

$m_2=4$:

  • $1 \times 30$
  • $2 \times 15$
  • $3 \times 10$
  • $5 \times 6$

$m_3=4$:

  • $1 \times 2 \times 15$
  • $1 \times 3 \times 10$
  • $1 \times 5 \times 6$
  • $2 \times 3 \times 5$

$m_4=1$:

  • $1 \times 2 \times 3 \times 5$

La multiplicación de las particiones $m_1,m_2,\dots,m_{\left\lfloor \sqrt{2 (k+1)}+1/2\right\rfloor}$ $p^k$ (donde $p$ es primo) están dadas por los coeficientes de la expansión de la serie $$f_1(x,k)=\dfrac{1}{\prod _{n=1}^k (1-x^n)}$$ where the $m$th partition is give by the $(m+ 1 - k(k - 1)/2)$th coeficiente.

f1[k_] := 1/Product[(1 - x^n), {n, 1, k}]
g1[a_, b_] := CoefficientList[Series[f1@b, {x, 0, b + a}], x][[1 - b (b - 1)/2 + a]]
h1[n_] := g1[n, #] & /@ Range@Floor[Sqrt[2 (n + 1)] + 1/2]

h1[#] & /@ Range@6

da

\begin{array}{c} 1 & 1\\ 1 & 1\\ 1 & 2 & 1\\ 1 & 2 & 1\\ 1 & 3 & 2\\ 1 & 3 & 3 & 1\\ \end{array}

por ejemplo $512$ tiene particiones de longitud $m_1=1,\ m_2=5,\ m_3=7,\ m_4=3$.

$m_1=1$:

  • $512$

$m_2=5$:

  • $1 \times 512$
  • $2 \times 256$
  • $4 \times 128$
  • $8 \times 64$
  • $16 \times 32$

$m_3=7$:

  • $1 \times 2 \times 256$
  • $1 \times 4 \times 128$
  • $1 \times 8 \times 64$
  • $1 \times 16 \times 32$
  • $2 \times 4 \times 64$
  • $2 \times 8 \times 32$
  • $4 \times 8 \times 16$

$m_4=3$:

  • $1 \times 2 \times 4 \times 64$
  • $1 \times 2 \times 8 \times 32$
  • $1 \times 4 \times 8 \times 16$

Sería bueno encontrar una solución generalizada para cualquier $p_i^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, pero no sé si esto es easiliy alcanzable.

3voto

Marko Riedel Puntos 19255

Permítanme presentar un comprobante de la primera especial del caso (producto de la $k$ distintos de los números primos) por @martin, que es un buen resultado que puede ser probada por Polya enumeración.

Voy a suponer que el lector ha consultado y comprendido el material en el siguiente MSE enlace el que no voy a repetir aquí.

Usando la notación desde el enlace con la a $q$ el número de factores en la partición obtenemos por el Polya Enumeración Teorema de la siguiente fórmula:

$$G(k, q) = \left[\prod_p X_p\right] Z(P_q)\left(\prod_p (1+X_p)\right) \quad\text{donde}\quad n=\prod_p p^v$$

con todos los $v=1$ y tenemos $k$ distintos de los números primos en el producto. Aquí el corchete indica el coeficiente de extracción de poder formal serie e $Z(P_q)$ es el ciclo del índice del conjunto de operador $\mathfrak{P}_{=q}$ que también fue utilizado en los vinculados a la computación desde arriba.

Ahora recuerdo la OGF del conjunto de operador que es $A$Z(P_q) = [z^q] \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).$$

Observar que en la sustitución en el ciclo del índice que permita $$a_m = \prod_p (1+X_p^m).$$

Pero el grado de $X_p$ en el coeficiente de ser extraído es uno, lo que significa que a partir de la $a_m$ $m\ge 2$ sólo el término constante contribuye, que es uno.

Esto le da a la fórmula

$$G(k, q) = \left[\prod_p X_p\right] [z^q] \exp\left(z\prod_p (1+X_p) - \frac{z^2}{2} + \frac{z^3}{3} - \frac{z^4}{4} + \cdots\right)$$

que es $$G(k, q) = \left[\prod_p X_p\right] [z^q] \exp\left(z\left(-1+\prod_p (1+X_p)\right) + \log(1+z)\right) \\ = \left[\prod_p X_p\right] [z^q] (1+z) \exp\left(z\left(-1+\prod_p (1+X_p)\right)\right) \\ = \left[\prod_p X_p\right] \left(\frac{1}{p!} \left(-1+\prod_p (1+X_p)\right)^q + \frac{1}{(p-1)!} \left(-1+\prod_p (1+X_p)\right)^{p-1}\right).$$

Haciendo coeficiente de extracción en el primer término nos encontramos $$\left[\prod_p X_p\right] \frac{1}{p!} \sum_{m=0}^p {q\elegir m} (-1)^{p-m} \prod_p (1+X_p)^m.$$

Sólo los términos con $X_p$ elevado a la potencia de uno de contribuir y obtenemos el primer término $$\frac{1}{p!} \sum_{m=0}^p {q\elegir m} (-1)^{p-m} m^k = {k\llave q}.$$

El segundo término es similar y por lo tanto la respuesta a la especial caso de un producto de $k$ de los números primos es

$${k\brace q} + {k\brace q-1}.$$

Ahora que tenemos esto nos puede dar una combinatoria interpretación. El primer término representa el caso en que se divide el $k$ factores primos de a $q$ no vacía de conjuntos que corresponden a las $q$ distintos factores de la multiplicación de la partición con ninguno de los factores siendo uno. (Con la $k$ de los números primos son diferentes, los productos de los elementos de estos conjuntos son necesariamente distintos.) Esta casi completa el recuento excepto que no se han contabilizado las particiones contiene uno como un factor. Que deja a $q-1$ factores diferentes a elegir de acuerdo con el mismo procedimiento que antes, de hecho.

Observación. El uso de la OGF de los números de Stirling del segundo tipo que es $${n\brace k} = [z^n] \prod_{r=1}^k \frac{z}{1-rz}$$

tenemos la generación de la función $$\prod_{i=1}^q \frac{z}{1-rz}+ \prod_{i=1}^{p-1} \frac{z}{1-rz} = \left(1+\frac{z}{1-qz}\right) \prod_{i=1}^{p-1} \frac{z}{1-rz} \\ = \frac{1-(q-1)z}{1-qz} \prod_{i=1}^{p-1} \frac{z}{1-rz}.$$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X