Formas de sumar 10 números entre 1 y 12 para obtener 70

Question

Sé que esto tiene algo que ver con los factoriales, y las combinaciones y permutaciones. He estado desconcertando sobre esto por un tiempo, y no puedo encontrar una respuesta. Mi pregunta es, ¿cómo se podría averiguar cuántas formas hay de usar exactamente 10 números del 1 al 12 para sumar 70? El orden es importante. Por lo tanto, permutaciones no combinaciones. ¡Gracias de antemano! :RE

Edición : No son necesariamente números distintos como en 12,12,12,12,12,2,2,2,2,2 funcionarían.

Answer 1

La generación de las funciones de trabajo, creo. Considere que el producto

$$(x + x^2 + \ldots + x^{12})^{10}$$

A continuación, el coeficiente de $x^{70}$ en el polinomio resultante es su respuesta: tenemos que escoger una potencia de cada factor (y podríamos tener el mismo poder varias veces, en diferentes factores, tales que su suma es igual a 70, y el orden no importa.

sacar el $x$ de cada término, tenemos el coeficiente de $x^{60}$ en

$$(1 + x + \ldots + x^{11})^{10}$$ para obtener la respuesta.

Escribimos el término de la $\frac{1-x^{12}}{1-x}$, por lo que necesitamos el coeficiente de $x^{60}$ en

$$(1 - x^{12})^{10} (1-x)^{-10}$$ y podemos ampliar este último con la (generalizada) teorema del binomio dos veces:

$$\left(\sum_{k=0}^{10} \binom{10}{k} (-1)^{k}x^{12k}\right)\left(\sum_{k=0}^{\infty} \binom{9+k}{k} x^k\right)\mbox{.}$$

Para obtener $x^{60}$, hay varias formas: en la mano izquierda se suma que tenemos los poderes $1,x^{12},\ldots,x^{60}$ a considerar con sus coeficientes de $1,-\binom{10}{1},\binom{10}{2},\ldots ,-\binom{10}{5}$ que se multiplica con sus competencias que complementan $x^{60},x^{48},\ldots,x^0$ y sus coeficientes de $\binom{69}{9},\binom{57}{9},\ldots,1$ respectivamente.

Así, obtenemos como respuesta $$\binom{69}{9} - \binom{10}{1}\binom{57}{9} + \binom{10}{2}\binom{45}{9} - \binom{10}{3}\binom{33}{9} + \binom{10}{4}\binom{21}{9} - \binom{10}{5}$$

Answer 2

No estoy seguro de que un algoritmo es lo que usted está buscando, pero por lo que vale la pena, aquí es un simple basado en el algoritmo de programación dinámica formada a partir de la siguiente relación de recurrencia:

Deje $f(n, x) = \text{number of ways to generate a sum of } x \text{ using exactly } n \text{ numbers from 1 to 12} $

A continuación, $f(n, x) = \sum\limits_{i=1}^{12}f(n-1, x-i)$

Usted está seleccionando el número de $i$, luego el resto de la suma sería de $x - i$, que se formó el uso de $n-1$ más números. Y usted puede seleccionar cualquiera de $1$ a $12$. $f(n, x) = 0$ si $x \le 0$.

Lo que quiero es $f(10, 70)$. Proceder en un enfoque de abajo arriba. Crear una $10$x$70$ matriz, donde el $i^{th}$ fila y $j^{th}$ columna almacena el valor de $f(i, j)$. Llenar la fila 1, que sería el caso base. Observe que el $i$ésima columna de la fila $1$ significa que el número de maneras de obtener una suma de $i$ $1$ número de $1 \dots 12$. Por lo tanto, $f(1, i) = 1$ si $1 \le i \le 12$, e $0$ lo contrario.

Proceder sucesivamente con el cálculo de las siguientes filas. Para cualquier fila, que requeriría sólo valores de la fila anterior, que ya calculada. Mantener este hasta llegar a la $10^{th}$ fila, y $70^{th}$ columna.

Este sería tedioso por la mano, sino con un pequeño código de computadora, este debe ser resuelto en una fracción de segundo.