¿Cuántas listas de 100 números (de 1 a 10) agregar a 700?

Question

Cada número es de uno a diez inclusive sólo. Hay $100$ los números en la lista ordenada. El total debe ser de $700$.

Cuántas de estas listas?

Nota: si, como sucede, este es uno de los problemas de matemáticas, donde sólo una aproximación que se conoce, eso sería genial. (Mi conjetura es que no es "que" las grandes, de alrededor de $10^{20}$ tal vez?)

Gracias!!

---

Así que, para ser claros decir que tienes un dado con las caras etiquetadas $1$-$10$. Que rollo es de $100$ veces, una vez cada 10 $de$ segundos en orden. El resultado es, si se quiere, una matriz específica de los $100$ los números (cada uno $de$1-$10$), cada posición de etiquetado $1$ para $100$. La matriz debe, a continuación, agregue $700$; cuántas de estas matrices??

---

Solo para ser absolutamente claro, creo que el total de "todos" en las listas (por lo tanto, no hay ningún requisito para agregar a $700$, ya que puede añadir a cualquier cosa), es, de hecho, simplemente $1$ googol, es decir, $10^{100}$.

Answer 1

La Generación De La Función De Enfoque

El coeficiente de $x^{700}$ en $(x+x^2+x^3+\dots+x^{10})^{100}$ es el número que buscas. Esto es porque cada elección de uno de los sumandos en cada término da una opción única para uno de los $100$ los números.

Podemos obtener una forma más fácil por primera notar que el coeficiente de $x^{700}$ de arriba es el coeficiente de $x^{600}$ en $(1+x+x^2+\dots+x^9)^{100}$ y que $$ \begin{align} (1+x+x^2+\dots+x^9)^{100} &=\left(\frac{1-x^{10}}{1-x}\right)^{100}\\ &=\sum_{j=0}^{100}\binom{100}{j}\left(-x^{10}\right)^j\sum_{k=0}^\infty\binom{-100}{k}(-x)^k\\ &=\sum_{j=0}^{100}\binom{100}{j}\left(-x^{10}\right)^j\sum_{k=0}^\infty\binom{k+99}{k}x^k\etiqueta{1} \end{align} $$ Ahora sólo tenemos que sumar las contribuciones a $x^{600}$ en $(1)$, que proviene de los términos que $k=600-10j$. Por lo tanto, el coeficiente de $x^{600}$ en $(1)$ es $$ \sum_{j=0}^{60}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j}\etiqueta{2} $$ lo que viene a $$ 12113063910758377468145174162592296408571398929\\1260198434849317132762403014516376282321342995 $$ o aproximadamente $1.2113063910758377468\times10^{92}$

---

Inclusión-Exclusión Enfoque

Para calcular el número de maneras para $100$ no de los números negativos a la suma de $600$, podemos usar la costumbre de las estrellas y las barras de enfoque que da $$ \binom{699}{600} $$ Cuántas de estas formas incluyen un número $10$ o más grande? Podemos tratar de contar en esta pegando un chunk de $10 dólares de estrellas en uno de los $100$ los lugares y contar cuántas maneras a la suma de $100$ los números a $600-10$. Esto le da $$ \binom{100}{1}\binom{689}{590} $$ pero este cuenta con el doble de las formas, que incluyen dos números $10$ o más grande. Para contar estas, nos atenemos $2$ trozos de $10 dólares de estrellas en dos de los $100$ plaes y contar cuántas maneras a la suma de $100$ los números a $600-20$. Esto le da $$ \binom{100}{2}\binom{679}{580} $$ Podemos aplicar Inclusión-Exclusión para obtener el número de maneras para $100$ no negativo números de menos de $10$ a la suma de $700$ para ser $$ \sum_{j=0}^{60}(-1)^j\binom{100}{j}\binom{699-10j}{600-10j} $$ que es el mismo que se ha metido en $(2)$.

Answer 2

En el lenguaje de las composiciones, lo que quieres son la cantidad de $Un$restringido composiciones de $n=700$ en $k=100$ donde $A=\{1,2,\ldots,\}$ con $a=10$. Mientras no conozco una forma cerrada para este número, se puede expresar tales contar sucintamente el uso formal de potencia de la serie. Para representar a nuestro conjunto $A$ de términos, utilizamos la formal polinomio $f_{a}(x)=\sum\limits_{j=1}^{a} x^j = \dfrac{x-x^{+1}}{1-x}$. Si tenemos la plaza de esto, entonces el coeficiente de un término $x^n$ representan el número de maneras en que dos enteros en $Un$ puede agregar a un total de $n$. Esto nos da el siguiente resultado:

La cantidad de $Un$restringido composiciones, con $A=\{1,2,\ldots\}$, $n$ en $k$ partes es el $$n th coeficiente de $f_{10}(x)^k$, que podemos expresar como $[x^n]\left(\dfrac{x-x^{+1}}{1-x}\right)^k.$

Así, en el caso de la mano de lo que queremos encontrar (o al menos estimar) es de $\boxed{\displaystyle\left[x^{700}\right]\left(\dfrac{x-x^{11}}{1-x}\right)^{100}}$. Sorprendentemente, este puede ser arrancados con bastante facilidad por WolframAlpha, cediendo el lugar impresionante resultado de $$ \boxed{ \begin{align} 12113063910758377468145174162592296408571398929 &\\ 1260198434849317132762403014516376282321342995 &\aprox 1.2 \times 10^{92} \end{align} } $$ Para aproximaciones, sugiero leer Sedgwick y Flajolet de la Analítica de la Combinatoria que está disponible para su descarga en el sitio de libreta. Me pueden cavar en allí mismo para ver si hay algo que se conoce o se puede estimar sobre esos números.

Answer 3

Tenga en cuenta que los números que se agregan juntos tenemos $\mu_0=11/2$ y una desviación estándar de $\sigma_0=\sqrt{33}/2$; por el teorema del límite central, la distribución de la suma de $100$ tal número es aproximadamente una Gaussiana con media $\mu=100\mu_0 = 550$ y una desviación estándar de $\sigma=10\sigma_0=5\sqrt{33}$. El continuo de la distribución Gaussiana es $$ f(x,\mu\sigma)=\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right); $$ y en una primera aproximación se puede ignorar la corrección de discreto. Por lo que el número al que desea es aproximadamente $$ N\aprox 10^{100} \cdot f(700,550,5\sqrt{33})=\frac{10^{100}}{5\sqrt{33}\sqrt{2\pi}}\exp\left(-\frac{150^2}{1650}\right)\\ = \frac{10^{100}}{5\sqrt{66\pi}}e^{-150/11}\approx 1.66\times 10^{92}. $$ Es útil para comparar esto con el resultado computacional. Una simple implementación de Python es la siguiente:

def N(x, n, cache={(0,0):1}):
   if x<0 or (n==0 and x>0): return 0
   if not cache.has_key((x,n)):
      cache[(x,n)] = sum([N(x-i, n-1) for i in xrange(1,11)])
   return cache[(x,n)]

A continuación, N(700, 100) * 1.0 rendimientos 1.2113063910758377e+92.

Answer 4

Para un cálculo de la respuesta, tengo alrededor de $1.21131 \cdot 10^{92}$ acabo de hacer una hoja de Excel con las filas marcadas -9 a través de 100 y columnas de la 1 a la 100. Las filas representan el número de maneras de hacer que la suma con el número de números de $1 a$ través $de$ 10 en el encabezado de la columna. En la columna 1, $1$ en cada fila de $1 a$ través $de$ 10. A continuación, en las columnas posteriores de cada celda es la suma de diez entradas en la columna a la izquierda, de uno sobre diez arriba. Las filas con números negativos en ellos hay, así que no tiene que cortar la década de sumas de dinero, como por una suma de $3$ de dos números.

Aquí está la esquina superior de la hoja:
$$ \begin {array} {l l l l l } tot&1&2&3&4\\ \hline 1&1&&&\\2&1&1&0&0\\3&1&2&1&0\\4&1&3&3&1\\5&1&4&6&4\\6&1&5&10&10\\7&1&6&15&20\\8&1&7&21&35\\9&1&8&28&56\\10&1&9&36&84\\11&&10&45&120\\12&&9&55&165\\13&&8&63&220\\14&&7&69&282\\15&&6&73&348\\16&&5&75&415\\17&&4&75&480\\18&&3&73&540\\19&&2&69&592\\20&&1&63&633\\21&&0&55&660\\22&&0&45&670\\23&&0&36&660\\24&&0&28&633\\25&&0&21&592\\26&&0&15&540\\27&&0&10&480\\28&&0&6&415\\29&&0&3&348\\30&&0&1&282\\31&&0&0&220\\32&&0&0&165\\33&&0&0&120\\34&&0&0&84\\35&&0&0&56\\36&&0&0&35\\37&&0&0&20\\38&&0&0&10\\39&&0&0&4\\40&&0&0&1\\ \end {array} $$

Answer 5

$\newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert}$ Con $\ds{0 < a < 1}$:

\begin{align} &\color{#66f}{\large\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10} \delta_{k_{1}\ +\ \cdots\ +\ x_{100},700}} =\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10}\oint_{\verts{z}\ =\ a} {1 \over z^{-k_{1}\ -\ \cdots\ -\ k_{100}\ +\ 701}}\,{\dd z \más de 2\pi\ic} \\[3 mm]&=\oint_{\verts{z}\ =\ a} {1 \over z^{701}}\,\pars{\sum_{k =1}^{10}z^{k}}^{100}\,{\dd z \más de 2\pi\ic} =\oint_{\verts{z}\ =\ a}{1 \over z^{701}}\,\pars{z\,{z^{10} - 1 \sobre z - 1}}^{100} \,\,{\dd z \más de 2\pi\ic} \\[3 mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{601}}\, {\pars{1 - z^{10}}^{100} \ \pars{1 - z}^{100}}\,\,{\dd z \más de 2\pi\ic} \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\pars{1} \\[3 mm]&=\sum_{n = 0}^{100}\sum_{k = 0}^{\infty}\pars{-1}^{n + k}{100 \elegir n} {-100 \elegir k}\oint_{\verts{z}\ =\ a}{1 \over z^{601 - 10n - k}} \,{\dd z \más de 2\pi\ic} \\[3 mm]&=\sum_{n = 0}^{100}\sum_{k = 0}^{\infty}\pars{-1}^{n + k}{100 \elegir n} \pars{-1}^{k}{k + 99 \elegir 99}\delta_{10n + k,600} =\sum_{n = 0}^{100}\pars{-1}^{n}{100 \elegir n}{699 - 10n \elegir 99} \end{align}

Contribuciones a la suma están limitados por $\quad\ds{0 \leq n \leq 100}\quad$ y $\quad\ds{99 \leq 699 - 10n}\quad$ que producen $\quad\ds{0 \leq n \leq 60}$:

$$ \color{#66f}{\large\sum_{k_{1}=1}^{10}\ldots\sum_{k_{100}=1}^{10} \delta_{k_{1}\ +\ \cdots\ +\ x_{100},700} =\sum_{n = 0}^{60}\pars{-1}^{n}{100 \elegir n}{699 - 10n \elegir 99}} $$ que es de $\ds{\pars{~\mbox{ver la expresión}\ \pars{1}~}}$, equivalente a $\ds{\bracks{z^{600}}\pars{1 - z^{10} \over 1 - z}^{100}}$.

Esto lleva a que el valor \begin{align}& {\tt 1.211306391075837746814517416259229640857139892912601984348493171327624} \\ &{\tt 03014516376282321342995 \times 10^{92}} \end{align}

Se encuentra con W & Una.