I was hoping somebody could help me out with this problem:
Solve by using generating functions: How many ways to collect \$3000 from 50 people, if each person gives at least \$2 and at most \$100.
I am struggling with how to model this as a generating function. Any help is appreciated.
Thanks!
The generating function for this problem would be $$(x^2+x^3+...+x^{100})^{50}$$ Since each person has to pay at least $2$ and at most $100$. Now we must find the coefficient of $x^{3000}$. It is generally a good idea to factor using geometric series. $$\left(\frac{x^2-x^{101}}{1-x}\right)^{50} = x^{100}\left(\frac{1-x^{99}}{1-x}\right)^{50}$$ So now we must find the coefficient of $x^{2900}$ of $$(1-x^{99})^{50}\cdot\left(\frac{1}{1-x}\right)^{50}=\sum_{n=0}^{50} (-x^{99})^n \binom{50}{n}^{50}\cdot \sum_{i=0}^{\infty}x^i \binom{i+49}{i}$$ For each $n$ we can find the coefficent of $x^{2900}$ by considering only the necessary part of the latter infinite sum as follows $$x^{2900}\sum_{n=0}^{29} (-1)^n \binom{50}{n} \binom{2900-99n+49}{2900-99n}$$ Note that we only sum to $29$ since for $n>29$, we have $2900-99n<0$. So now we have an answer (I don't see a nice way to sum this atm, so I decided wolframalpha is good). $$ \sum_{n=0}^{29} (-1)^n \binom{50}{n} \binom{2900-99n+49}{2900-99n}=10028725266150361737032769781564$$$$85933447776326227073868507419414908597259264659682770744123421831$$