Coefficient of x to the Power 9 in Polynomial Expansion

To find the coefficient of $x^9$ in the polynomial expansion of $P(x) = (1 + x)(1 + x^2)(1 + x^3) \dots (1 + x^{100}) = \prod_{k=1}^{100} (1 + x^k)$

we observe that factors $(1 + x^k)$ for $k > 9$ will only contribute $1$ towards the term $x^9$. Therefore, the coefficient of $x^9$ in $P(x)$ is identical to the coefficient of $x^9$ in the truncated product: $Q(x) = \prod_{k=1}^{9} (1 + x^k) = (1 + x)(1 + x^2)(1 + x^3)\dots(1 + x^9)$

When expanding $Q(x)$, a term $x^9$ is formed by selecting either $1$ or $x^k$ from each factor $(1 + x^k)$ such that the sum of the exponents of the selected factors equals $9$. Since each exponent $k \in \{1, 2, \dots, 9\}$ can be chosen at most once, the coefficient of $x^9$ is equal to the number of partitions of $9$ into distinct positive integers.

We list all possible partitions of $9$ into distinct positive integers grouped by the number of parts:

1. Partitions with $1$ part:

   • $9$ (1 partition)

2. Partitions with $2$ distinct parts:

   • $1 + 8$
   • $2 + 7$
   • $3 + 6$
   • $4 + 5$ (4 partitions)

3. Partitions with $3$ distinct parts:

   • $1 + 2 + 6$
   • $1 + 3 + 5$
   • $2 + 3 + 4$ (3 partitions)

4. Partitions with $4$ or more distinct parts:

   • The smallest possible sum of 4 distinct positive integers is $1 + 2 + 3 + 4 = 10 > 9$. Thus, no such partitions exist.

Summing up the partitions across all cases: $\text{Total coefficient} = 1 + 4 + 3 = 8$

Thus, the coefficient of $x^9$ in the given expansion is $8$.