Encuentre la cantidad de soluciones $$ x_1+x_2+x_3+x_4+x_5+x_6+x_7 = 7 \text{ such that } \forall_i x_i \in \left\{0,1,2\right\}$ $ Sé cómo puedo hacer esto cuando no tengo la restricción $\forall_i x_i \in \left\{0,1,2\right\}$ : $$ ooooooooooooo \text{ n+(k-1) = 7 + (7-1) = 13 balls }$ $ $$ oo||o|oo|o|o| \text{ k-1 = 6 balls I replace with sticks }$ $ y tengo $$ 2 + 0 + 1 + 2 + 1 + 1 + 0 = 7 $ $ Puedo hacer esto en $$ \binom{n+k-1}{k} = \binom{13}{7} $ $ maneras. ¿Pero cómo lidiar con la restricción adicional?
Respuestas
¿Demasiados anuncios?
Matthew Scouten
Puntos
2518
Mike Earnest
Puntos
4610
Sugerencia: Usted desea que el coeficiente de $x^7$en $$ (1+x+x^2)^7=\left(\frac{1-x^3}{1-x}\right)^7=(1-x^3)^7\times (1-x)^{-7} $$ Ahora, $(1-x^3)^7$ e $ (1-x)^{-1}$ son las funciones de generación de dos buenas series, $a_n$ e $b_n$; podemos encontrarlos? Una vez que usted hace, porque usted desea que la convolución de estas dos series: $$ \sum_{k=0}^7 a_kb_{n-k}. $$ Además, usted encontrará que $a_k$ es igual a cero, a menos que $k$ es un múltiplo de a$3$, por lo que la suma se tiene sólo tres a cero y por lo tanto fácilmente computable a mano.
El número de combinaciones únicas de números sumados para lograr $7$ de tal manera son $$\{1,1,1,1,1,1,1\}$ $ $$\{2,1,1,1,1,1\}$ $ $$\{2,2,1,1,1\}$ $ $$\{2,2,2,1\}$ $ Así que el número total de soluciones es dado por $$\frac{7!}{7!}+\frac{7!}{5!}+\frac{7!}{3!\cdot2!\cdot2!}+\frac{7!}{3!\cdot3!}=393$ $
Mark Fischler
Puntos
11615
La "forma cerrada respuesta" para el número de maneras de asignar $\{x_1, x_2, \cdots ,x_k\}$ tal que $\forall n : x_n \in \{0,1,2\}$ e $\sum_{n=1}^k x_n = k$ es, por extraño $k$ $$ F^{-\frac{k}2, -\frac{k-1}2}_1(4) $$ y para $k$ $$ F^{-\frac{k-1}2, -\frac{k}2 }_1(4) $$ Estos $F^{a,b}_c$ son funciones hipergeométricas.
Este se obtiene dejando $n$ el número de $2$s utilizado y haciendo $$ \sum_{n=0}^\left\lfloor{\frac{k}2}\right\rfloor \binom{k}{n}\binom{k-n}{k-2n} $$ y el uso de las técnicas que se exponen en Concreto de las Matemáticas.
Martin Hansen
Puntos
68
A partir de la teoría de Funciones de Generación es claro que la respuesta se reduce a encontrar el coeficiente de $x^7$ en $(1 + x + x^2)^7$,
Escribir el equivalente de Triángulo de Pascal para que el Trinomio Coeficientes, o buscar, o escriba un breve programa para generar ellos (cada término es la suma de los tres términos, arriba a la izquierda, justo encima de, arriba a la derecha) $$1$$ $$1 : 1 : 1$$ $$1: 2: 3: 2: 1$$ $$1: 3: 6: 7: 6: 3: 1$$ $$1: 4: 10: 16: 19: 16: 10: 4: 1$$ $$1: 5: 15: 30: 45: 51: 45: 30: 15: 5: 1$$ $$1: 6: 21: 50: 90: 126: 141: 126: 90: 50: 21: 6: 1$$ $$1: 7: 28: 77: 161: 266: 357: 393: 357: 266: 161: 77: 28: 7: 1 $$ El número buscado es el centro del coeficiente de la Fila 7, el 393.
