2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.