How many ways to get the terms of sequence 1-100 sum up to 9?

49 Views Asked by At

I stumbled upon this in a binomial expansion problem where I was supposed to find the coefficient of $x^9$ in $$\prod_{i=1}^{100}{(1+x^i)}$$ The problem is simple enough, all I need to do is to find the coefficient of $x^9$ in the factors up till $(1+x^9)$, which I did through mindless labour by finding out all the possible singlets, pairs and triplets, but I'm not satisfied with it.

Isn't there a better, more subtle way to approach this? One thing that comes to my mind is using the number of integral solutions of: $$x_1=9\\ x_1+x_2=9\\ x_1+x_2+x_3=9$$

1

There are 1 best solutions below

3
On BEST ANSWER

You are on the right track. You are looking for the number of partitions of $9$ into distinct parts, and since $1+2+3+4=10>9$ there only are partitions with $1,2$ or $3$ parts. There obviously are four partitions with two parts and a single partition with one part. Counting the solutions of $$ a+b+c = 9 $$ with $a>b>c>0$ is the same as counting the solutions of $$ (C+B+A)+(C+B)+C = 9\quad \text{or}\quad 3C+2B+A=9$$ with $A,B,C\in\mathbb{N}^+$. $2B+A=6$ has $2$ solutions and $2B+A=3$ has $1$ solution, hence

$$ [x^9]\prod_{k\geq 1}\left(1+x^k\right) = 4+1+2+1 = \color{red}{8}.$$