El coeficiente de $x^9$ en la expansión de $(1+x)(1+x^2)(1+x^3)\cdots(1+x^{100})?$

Question

¿Cuál es el coeficiente de $x^9$ en la expansión de $(1+x)(1+x^2)(1+x^3)\cdots (1+x^{100})?$

---

Yo manualmente expandido $(1+x)(1+x^2)(1+x^3)...(1+x^{10})$ y se calcula el coeficiente de $x^9$$8$, pero no sé cómo resolverlo sin la expansión.Por favor me ayude.

Answer 1

Creo que el problema se reduce a contar el número de maneras de escribir $9$ como una suma de distintas, enteros positivos. No es el caso trivial de $9=9$, y que, además de tratar con la mano para coger todos los otros casos como el de $1+3+5$, $1+2+6$, etc. Creo que su mejor apuesta es a la fuerza bruta de este problema; una de esas veces en las que simplemente es más fácil de considerar cada caso que a la búsqueda de una solución elegante. Mi razonamiento es el siguiente:

Pensar en el producto $$\prod_{n=1}^{100} (1+x^n)$$ as a potential game of telephone where a "message" is passed from one parenthetical quantity to the next via multiplication. In each passage the message can either go to $1$ or $x^n$. For example, we could start at $1$ in $(1+x)$, then go to $1$ in $(1+x^2)$ and $\ldots$ and go to $1$ in $(1+x^{99})$ and lastly go to $x^{100}$ in $(1+x^{100})$ , which is to say we get $1^{99}\cdot x^{100} = x^{100}$ at the end of that particular sequence of multiplication. So we'll expect at least one quantity of $x^{100}$ in the fully expanded product. I'll call "getting $x^{100}$ out of that particular sequence of multiplication" the result of that message. More generally, the coefficient $R_p$ that appears on $x^p$ in the fully expanded product $$\prod_{n=1}^{100} (1+x^n) = R_0+R_1x^1+R_2x^2+\ldots +R_px^p +\ldots + R_{5050}x^{5050}$$ tells us the number of ways our message resulted in $x^p$.

Esperemos que la analogía es clara. Desde ahora estamos interesados en el coeficiente de $x^9$ aquí es por qué dije lo que hice en mi primer párrafo. Necesitamos saber cuántas maneras hay para pasar un mensaje a través del producto de manera que los resultados en $x^9$ al final. Una posible vía sería empezar a $x$, pasan a $x^2$, pasan a $1$$(1+x^3)$, pasan a $1$$(1+x^4)$, pasan a $1$$(1+x^5)$, pasan a $x^6$. En este punto nos tiene que pasar a $1$ en el resto de la $(1+x^n)$'s. De lo contrario, al final del mensaje, tendremos $x^p$ $p>9$ al final. El camino que acabo de mencionar los resultados en $$x^1\cdot x^2 \cdot 1^3 \cdot x^6 \cdot 1^{94} = x^9$$ which works because the sum of exponents on each $x$ in the product, $1+2+6$ sums to $9$. Hence you really do just want to count the number of ways to write $9$ as a sum of distinct, positive integers; much easier than computing the entire product. I concur that $R_9 = 8$.

Answer 2

El coeficiente de $x^9$ es el número de particiones de $9$ en partes distintas, es decir, el número de maneras de escribir $9$ como la suma de los distintos números enteros positivos cuando el orden de los sumandos no importa. La secuencia de estos números es OEIS A000009, y como se puede ver, no hay bella fórmula. Sin embargo, para un pequeño $n$ no es difícil escribir las particiones a mano: $9$, $8+1$, $7+2$, $6+3$, $5+4$, $6+2+1$, $5+3+1$, y $4+3+2$.

Answer 3

En cada uno de los factores de su producto, usted tendrá que elegir el $1$ o de la $x^i$, por lo que inmediatamente vemos que para todos los factores de con $i > 9$ tenemos que escoger el $1$, de lo contrario nos pondremos $x^k$$k > 9$. Así que sólo podemos ver en el producto hasta $(1 + x^9)$. Ahora nos fijamos en el número de formas de seleccionar $1$ $x^i$ aquí de tal manera que podamos acabar con $x^9$. Porque todos nuestros coeficientes se $1$, no necesitamos que preocuparse de aquellos, y sólo cuenta el número de maneras.

Para simplificar esto, supongamos que escoger siempre el $1$ si no se escriben, entonces todas las posibles combinaciones son: $x^9, x^1\cdot x^8, x^2\cdot x^7, x^3\cdot x^6, x^4\cdot x^5, x^1\cdot x^2\cdot x^6, x^1\cdot x^3\cdot x^5, x^2\cdot x^3\cdot x^4$ lo que nos da $8$ como el resultado final.

No es difícil ver que esto es equivalente a la suma de los números de $1, \ldots 9$ $9$el uso de cada número sólo una vez, y luego contar el número de sumatorias.