22 votos

De cuántas maneras puede $1000000$ ser expresado como producto de cinco números enteros positivos?

Estoy tratando de resolver el siguiente problema:

"¿En cuántas formas puede la cantidad de $1000000$ ser expresado como producto de cinco números enteros positivos?"

Aquí va mi intento:

Desde $1000000 = 2^6 \cdot 5^6$, cada uno de sus divisores tiene la forma $2^a \cdot 5^b$, y una descomposición de 1000000 en un producto de cinco factores tiene la forma $$ 1000000 = (2^{a_1} \cdot 5^{b_1})(2^{a_2} \cdot 5^{b_2})(2^{a_3} \cdot 5^{b_3})(2^{a_4} \cdot 5^{b_4})(2^{a_5} \cdot 5^{b_5}) $$ donde $a_i$ y $b_i$ son números enteros no negativos y que satisfagan las condiciones $$ a_1 + a_2 + a_3 + a_4 + a_5 = 6, b_1 + b_2 + b_3 + b_4 + b_5 = 6 $$ El número total de sistemas de $a_i$ que satisface la primera ecuación es de $210$ y el mismo número es de $b_i$. Así, el número total de descomposición es de $210 \cdot 210 = 44100$. Sin embargo, en esta enumeración, factorizations que difieren sólo en la brder de los factores que han sido contados por separado; es decir, algunos factorizations se cuentan varias veces cada uno.

Para obtener el número de los distintos desordenada descomposiciones me debe, en primer lugar, reste el número de ordenadas descomposiciones con al menos dos idénticos factores y, en segundo lugar, dividir el número resultante por $5!$ para dejar sólo desordenada.

Y estoy atascado en el paso de contar el número de ordenadas descomposiciones con al menos dos idénticos factores. El número de descomposiciones con $k$ idénticos factores es de $(\lfloor\dfrac{a}{k}\rfloor + 1)(\lfloor\dfrac{b}{k}\rfloor+1){5 \elegir k}$, es decir, el número de descomposiciones con idénticos dos factores es de $16 \cdot {5 \elegir 2} = 160$, tres idénticos factores - $9 \cdot {5 \elegir 3} = 90$, cuatro - $4 \cdot {5 \elegir 4} = 20$ y cinco - $4 \cdot {5 \elegir 5} = 4$. Por lo tanto el número de distintas descomposiciones debe ser igual a $\dfrac{44100-160-90-20-4}{5!}$, pero este número no es integral. Supongo que el número de descomposiciones con $k$ idénticos factores se superponen y yo uso indebido de inclusión-exclusión principio. Pero no tengo idea de cómo me puede contar que se superponen las descomposiciones.

Por favor, ayuda! Gracias!

17voto

smitchell360 Puntos36

El número en cuestión es el coeficiente de $x^6 y^6 z^5$ en el producto $$\prod_{0\le i,j\le 6}(1+x^i y^j z).$$ Aquí $z$ cuenta el número de factores (queremos $5$); $x$ y $y$ la etiqueta de los poderes de $2$ y $5$ respectivamente; queremos tanto de los $6$. La distinción está garantizada debido a que, para cada factor de $2^i 5^j$, tenemos que incluir una vez (multiplicando por $x^i y^j z$) o que no lo incluyen (y multiplicar por $1$).

Multiplicando todo el producto es difícil de manejar, pero se puede calcular que el mod $(x^7,y^7)$, lo que elimina un lío de términos que usted no necesita. El coeficiente de $x^6 y^6$ resulta ser $$5 z^7+64 z^6+194 z^5+235 z^4+123 z^3+24 z^2+z$$ que enumera el número de maneras de escribir de $1000000$ como un producto de $k$ factores diferentes, para todos los valores de $k$. Tomando $k=5$ confirmamos Cristiana de la respuesta de $194$.

7voto

Marko Riedel Puntos19255

Deje que $F(n)$ ser la manera en la que el número de 10 $^$ n se puede expresar como un producto de cinco números enteros positivos. Utilizando la misma estrategia como en este MSE enlace (el Poli Enumeración Teorema o PET), obtenemos la siguiente respuesta en términos de el ciclo del índice $Z(P_5)$ de el operador de conjuntos $\mathfrak{P}_{=5}:$

$$[A^n B^n] Z(P_5)\left(\frac{1}{1}\frac{1}{1-B}\right).$$

El ciclo de índice $A$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{3 }}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2} \\-1/4\,a_{{4}}a_{{1}}-1/6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}.$$

El sustituido ciclo de índice, a continuación, se convierte en $${\frac {1}{120\, \left( 1-\right) ^{5} \left( 1-B \right) ^{5}}} \\-1/12\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( 1-\right) ^{3} \left( 1-B \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) \left( 1-\right) ^{2} \left( 1-B \right) ^{2}}}\\+1/8\,{\frac {1 }{ \left( 1-\right) \left( 1-B \right) \left( -{A}^{2}+1 \right) ^{2} \left( -{B}^{2}+1 \right) ^{2}}}\\-1/4\,{\frac {1}{ \left( -{A}^{4}+1 \right) \left( -{B}^{4}+1 \right) \left( 1-a \right) \left( 1-B \right) }}\\-1/6\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) }}\\+1/5\,{\frac {1}{ \left( -{A}^{5}+1 \right) \left( -{B}^{5}+1 \right) }}.$$

La extracción de los coeficientes de esto podemos obtener las piezas de $$A_1 = \frac{1}{120} {n+4\elegir 4}^2,$$ $$A_2 = -\frac{1}{12} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {n-2t+2\elegir 2} \right)^2,$$ $$A_3 = \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} {n-3t+1\elegir 1} \right)^2,$$ $$A_4 = \frac{1}{8} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {q+1\elegir 1}\right)^2,$$ $$A_5 = -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2,$$ $$A_6 = -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3t\equiv 0\mod 2]]\right)^2,$$ y $$A_7 = \frac{1}{5} [[n\equiv 0\mod 5]].$$

Esto produce que la fórmula cerrada $$\frac{1}{120} {n+4\elegir 4}^2 - \frac{1}{48} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} (n-2t+2)(n-2t+1)\right)^2 \\ + \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} (n-3t+1)\right)^2 + \frac{1}{32} (\lfloor n/2 \rfloor + 1)^2(\lfloor n/2 \rfloor + 2)^2 -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2 \\ -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3t\equiv 0\mod 2]]\right)^2 + \frac{1}{5} [[n\equiv 0\mod 5]].$$

Adicional simplificación es posible aquí, pero no aparece para agregar para la comprensión del problema. La secuencia que se obtiene a partir de $n=1$ es $$0, 0, 1, 12, 53, 194, 548, 1369, 3064, 6355, 12295, 22608, \\ 39658, 66992, 109357, 173435, 267890, 404494, 598065, 868065, \ldots$$ lo que está en acuerdo con la anterior respuesta.

También obtenemos $$F(1000) = 14758828112205481602.$$

4voto

user84413 Puntos16027

Hay 5 tipos de posibilidades para la desordenada exponentes $a_1,\cdots,a_5$ por 2:

$\textbf{1)}$ $6+0+0+0+0,\;\; 2+1+1+1+1$ $\;\;$(4 de una clase)

$\textbf{2)}$ $5+1+0+0+0,\;\; 3+0+1+1+1,\;\;4+2+0+0+0$ $\;\;$(3 de una clase)

$\textbf{3)}$ $4+1+1+0+0,\;\; 0+2+2+1+1$ $\;\;$(2 pares)

$\textbf{4)}$ $3+3+0+0+0,\;\; 0+0+2+2+2$ $\;\;$(casa completa)

$\textbf{5)}$ $3+2+1+0+0$ $\;\;$ (1 par)


Ya que tenemos el mismo 5 de posibilidades para el desordenada exponentes $b_1,\cdots,b_5$ 5,

podemos contar el número de maneras en que a la par de estos tipos para obtener distintos divisores, utilizando el hecho de que los dígitos que coinciden con dígitos repetidos deben ser distintos, y su orden no importa:

$\textbf{1)}$ y 5) $\;$y$\;$ $\textbf{5)}$ y 1): $\;\;\;2(2\cdot1)(1)={\color{rojo}4}$ maneras

$\textbf{2)}$ y 2): $\hspace{1.03}\;\;\;(3\cdot3)(1)={\color{rojo}9}$ maneras

$\textbf{2)}$ y 3) $\;$y$\;$ $\textbf{3)}$ y 2): $\;\;\;2(3\cdot2)(2)=\color{red}{24}$ maneras

$\textbf{2)}$ y 5) $\;$y$\;$ $\textbf{5)}$ y 2): $\;\;\;2(3\cdot1)(1+2\cdot3)=\color{red}{42}$ maneras

$\textbf{3)}$ y 3): $\hspace{1.03}\;\;\;(2\cdot2)(1+2\cdot2)=\color{red}{20}$ maneras

$\textbf{3)}$ y 4) $\;$y$\;$ $\textbf{4)}$ y 3): $\;\;\;2(2\cdot2)(1)=\color{red}{8}$ maneras

$\textbf{3)}$ y 5) $\;$y$\;$ $\textbf{5)}$ y 3): $\;\;\;2(2\cdot1)(2\cdot3+3\cdot2)=\color{red}{48}$ maneras

$\textbf{4)}$ y 5) $\;$y$\;$ $\textbf{5)}$ y 4): $\;\;\;2(2\cdot1)(3)=\color{red}{12}$ maneras

$\textbf{5)}$ y 5): $\hspace{1.03}\;\;\;3\cdot3+3\cdot3\cdot2=\color{red}{27}$ maneras


Esto da un total de $\color{red}{194}$ formas de expresar los $10^6$ como un producto de 5 diferentes números enteros positivos.

3voto

CodingBytes Puntos102

Hay 49 números de la forma $2^\alpha 5^\beta$ con $0\leq\alpha\leq6$ y $0\leq\beta\leq 6$, y hay ${49\elegir 5}=1\,906\,854$ conjuntos de cinco diferentes tales números. Fuera de estos cinco elementos de los conjuntos de exactamente $194$ producto $10^6$. He encontrado este uso de la fuerza bruta. El manejo de la condición de que los cinco factores debe ser diferente de una manera "automática" parece trascender la habitual inclusión-exclusión principio.

3voto

nczksv Puntos163

Para $n{\ge}0$, $\;$ deje que $F(n)$ ser la manera en la que el número de 10 $^$ n se puede expresar como un producto de cinco números enteros positivos.

Entonces $$F(n)=\left(\frac{1}{5!}\right)\left(24\left(\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n-1}{5}\right\rfloor\right)^{2} +(-30)\left(\left\lfloor\frac{n}{4}\right\rfloor+1\right)^{2} +(-20)\left(\left\lfloor\frac{n+2}{2}\right\rfloor-\left\lfloor\frac{n+2}{3}\right\rfloor\right)^{2} +20\left(\left\lfloor\frac{(n+2)(n+3)}{6}\right\rfloor\right)^{2} +15\left(\frac{2n^{2}+10n+11+(2n+5)(-1)^n}{16}\right)^{2} +(-10)\left(\frac{4n^{3}+30n^{2}+68n+45+3(-1)^{n}}{48}\right)^{2} +\left(\frac{(n+1)(n+2)(n+3)(n+4)}{24}\right)^{2} \right)$$

La respuesta para esta pregunta es de $F(6)=194$.

$$F(10)=6355,\quad F(100)=175519523577,\quad F(1000)=14758828112205481602.$$

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: