What is the coefficient of $x^9$ in the expansion of $(1+x)(1+x^2)(1+x^3)\cdots (1+x^{100})?$
I manually expanded $(1+x)(1+x^2)(1+x^3)...(1+x^{10})$ and calculated the coefficient of $x^9$ as $8$ but i dont know how to solve it without expanding.Please help me.
I think the problem boils down to counting the number of ways to write $9$ as a sum of distinct, positive integers. There is the trivial case of $9=9$, and besides that try by hand to catch all other cases like $1+3+5$, $1+2+6$, etc. I think your best bet is to brute force this problem; one of those times where it's just easier to consider every case than to search for an elegant solution. My reasoning is as follows:
Think of the product $$\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$.
Hopefully the analogy is clear. Since we now are interested in the coefficient of $x^9$ here is why I said what I did in my first paragraph. We need to know how many ways there are to pass a message through the product so that it results in $x^9$ by the end. One possible path would be to start at $x$, pass to $x^2$, pass to $1$ in $(1+x^3)$, pass to $1$ in $(1+x^4)$, pass to $1$ in $(1+x^5)$, pass to $x^6$. At this point we have to pass to $1$ in the rest of the $(1+x^n)$'s. Otherwise at the end of the message we'll have $x^p$ with $p>9$ at the end. The path I just mentioned results in $$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$.
The coefficient of $x^9$ is the number of partitions of $9$ into distinct parts, i.e., the number of ways of writing $9$ as the sum of distinct positive integers when the order of the summands doesn’t matter. The sequence of these numbers is OEIS A000009, and as you can see there, there is no nice formula. However, for small $n$ it’s not hard to write out the partitions by hand: $9$, $8+1$, $7+2$, $6+3$, $5+4$, $6+2+1$, $5+3+1$, and $4+3+2$.
In every factor of your product, you will need to pick either the $1$ or the $x^i$, so immediatly we see that for all factors with $i > 9$ we need to pick the $1$, otherwise we will get $x^k$ with $k > 9$. So we can just look at the product up till $(1 + x^9)$. Now we look at the number of ways to pick $1$ and $x^i$ here such that we end up with $x^9$. Because all our coefficients are $1$, we do not need to worry about those, and count only the number of ways.
To simplify this, assume you always pick the $1$ if you don't write them down, then all possible combinations are: $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$ which gives us $8$ as the final result.
It is not hard to see that this is equivalent to summing numbers $1, \ldots 9$ to $9$ using every number only once, and then counting the number of summations.
