En cuántos diferentes a partir de un conjunto de números de una suma fija se consigue?

Question

Tengo un conjunto de número, y quiero saber en cuántas maneras de establecer con cada número se utiliza cero, una o más veces una cierta suma en todo caso, ser logrado. No importa el orden. Por ejemplo, yo tengo una suma de '10' y el conjunto de [1,2] y quiero saber de cuántas maneras puede 1 y 2 se suman para llegar a 10. Sí, '1' y '2' tienen que ser utilizados más de una vez.

Ejemplo

10 = 1 + 1 + 2 + 2 + 2 + 2

10 = 1 + 1 + 1 + 1 + 2 + 2 + 2

10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

...

Hay más posibilidades para el ejemplo de la suma. No necesito la forma en que la suma es llegado yo.e (10 = 1 + 1 + 2 + 2 + 2 + 2 o 10 = 1 + 1 + 2 + 2 + 2 + 2 ...) cuántas combinaciones de '1' y '2' dame 10. Estoy trabajando con grandes conjuntos y números, así de simple enfoque será muy útil. Gracias

No, el no importa el orden de la suma. Si es 10 = 2* + 4*o 4* + 2*uno o cualquier otra permutación de ellos. El intento que hice implica el uso de un ordenador. Yo estaba pensando en algo como esto.

for (i = 0; i < sum/i; i++):
    for (j = 0; j<sum/j; j++):
        if (num1*i + num2*j == sum):
            numberOfWays +=1

Pero esto no es útil para grandes conjuntos como varios bucles for anidados son engorrosos. Estoy buscando una solución elegante.

ACTUALIZACIÓN de UN número puede ser utilizado 0 veces.

Answer 1

Podemos utilizar funciones de generación.

Tome su ejemplo de escritura de n como suma de $1$s y $2$s, representan el número de posibles $1$s como

$$x^{0\cdot 1}+x^{1\cdot 1}+x^{2\cdot 1}+x^{3\cdot 1}+\cdots$$

¿Qué es $x$? Usted podría preguntar, así que no es nada, no tiene ningún valor más allá de la formalidad de lo que nos permite escribir una lista de posibles $1$s en nuestra suma. E. g. $x^{3\cdot 1}$ indica la posibilidad de una suma con tres $1$s.

Podemos hacer lo mismo con el número de posibles $2$s por el listado

$$x^{0\cdot 2}+x^{1\cdot 2}+x^{2\cdot 2}+x^{3\cdot 2}+\cdots$$

Ahora ya que estamos interesados en todas las combinaciones de $1$ $2$ adicional, si multiplicamos estas dos listas como si fueran de la serie, a continuación, cada una de las resultantes plazo representará una posible suma, esto se llama una función de la generación de

$$(x^{0\cdot 1}+x^{1\cdot 1}+x^{2\cdot 1}+x^{3\cdot 1}+\cdots)(x^{0\cdot 2}+x^{1\cdot 2}+x^{2\cdot 2}+x^{3\cdot 2}+\cdots)\tag{1}$$

Así que la expansión se han términos como tu primer ejemplo, $x^{2\cdot 1+4\cdot 2}=x^{10}$ y el coeficiente de en frente de este plazo será el número de veces que la suma de $10$ puede ser alcanzada usando $1$s y $2$s.

Somos capaces de utilizar la expansión $(1-u)^{-1}=1+u+u^2+u^3+\cdots$ y la diferencia entre dos cuadrados $a^2-b^2=(a-b)(a+b)$ a nos ayudan a expresar el producto $(1)$

$$\frac{1}{(1-x)(1-x^2)}=\frac{1}{(1-x)^2(1+x)}\tag{2}$$

que puede ser escrito utilizando fracciones parciales

$$\begin{align}\frac{1}{(1-x)^2(1+x)}&=\frac{1}{2(1-x)^2}-\frac{1}{4(1-x)}+\frac{1}{4(1+x)}\\[1ex] &=\frac{1}{2}\sum_{n\ge 0}\binom{n+1}{1}x^n - \frac{1}{4}\sum_{n\ge 0}x^n+\frac{1}{4}\sum_{n\ge 0}(-1)^nx^n\\[1ex] &=\sum_{n\ge 0}\frac{2(n+1)+1+(-1)^n}{4}x^n\end{align}$$

Por lo tanto, en el caso simple de $1$s y $2$s podemos derivar una fórmula

$$\text{required count using $1$s and $2$s}=\frac{2(n+1)+1+(-1)^n}{4}$$

Así, por ejemplo, para una suma de $n=10$ hay $(2\cdot 11+1+1)/4=24/4=6$ sumas posibles.

Es posible obtener fórmulas para grandes conjuntos de posibles partes (no sólo de las partes de tamaño $1$$2$), pero las matemáticas se hace más largo aliento. En general es mejor utilizar los productos de la serie como $(1)$ obtener un $2$ dimensiones de recurrencia (un poco como el Triángulo de Pascal) para calcular los coeficientes.

Un ejemplo de la generación de la función de las sumas que implican $1$s, $2$s y $3$s es

$$\dfrac{1}{(1-x)(1-x^2)(1-x^3)}$$

deriva de la misma forma como por su ejemplo.

Answer 2

Este es un problema clásico para la generación de funciones. Representan el número de maneras de representar el $n$ como el coeficiente de $n$ en un poder formal de la serie. Si usted acaba de $1$ disponible, no sería una manera para representar cada número y la generación de función sería la $1+x+x^2+x^3+\ldots,$ que podemos formalmente suma a $\frac 1{1-x}$. Del mismo modo, si usted acaba de $2$ disponible sólo podía representar números y la serie iba a ser $1+x^2+x^4+\ldots=\frac 1{1-x^2}$ Si tiene $1$s y $2$s disponibles, multiplicar, por lo que el número de maneras de escribir $10$ es el coeficiente de $x^{10}$ en la serie de $\frac 1{(1-x)(1-x^2)}$, $6$ por Alfa Cuando usted tiene sólo dos sumandos es mucho más fácil porque se puede elegir el número de doses en $6$ formas, desde la $0$$5$, luego rellenar con.