# Combinatorics-Generating function

5 pirates find 3000 gold coins. In how many ways they can distribute them, if the captain gets at least 500 and not more then 2000 coins. the rest get at least 150 but not more then 1000 coins.(each one)

I've tried to use this generating function: $(x^{150}+x^{151}+...+x^{1000})^4 * (x^{500}+x^{501}+...+x^{2000})$

Then I thought this approach is better:

we will try to decide how many coins the othe four get, and the pirate will have one option... then, we need to solve: $t_1+t_2+t_3+t_4=n$ where $t_1,t_2,t_3,t_4$ between 150, 2000 and $n$ is: $1000,1001,....,2500$ because $t_i$ is at least 150, we can solve: $y_1+y_2+y_3+y_4=n-600$ we only need to sum the solutions for any $n$ in range. I couldn't solve it, I don't know how to insert the condition that $t_i\leq1000$

Thank You.

We can solve from the generating function itself, rewriting it as:

\displaystyle \begin{align} g(x)&= \dfrac{x^{600}\,(1-x^{851})^4}{(1-x)^4}\cdot \dfrac{x^{500}\,(1-x^{1501})}{(1-x)}\\\\ &=\dfrac{x^{1100}\,(1-x^{851})^4\,(1-x^{1501})}{(1-x)^5} \end{align}

Expand:

\begin{align} g(x)&=\left(x^{1100}-x^{2601}\right)\, \left(1-\binom{4}{1}x^{851}+\binom{4}{2}x^{1702}-\binom{4}{3}x^{2553}+\binom{4}{4}x^{3404}\right)\sum_{n=0}^{\infty}\binom{n+4}{4}x^n \end{align}

Extract $[x^{3000}]$, which is:

$\displaystyle \binom{4}{0}\, \binom{1904}{4}-\binom{4}{1}\, \binom{1053}{4}+\binom{4}{2}\, \binom{202}{4}-\binom{403}{4}=341444579376$

• Here's a code in Sage to extract the required coefficient: code – gar Apr 11 '14 at 8:10
• Can you explain how you got the final expression with the binomial coefficients? – ShreevatsaR Apr 11 '14 at 9:10
• It looks similar to Inclusion–exclusion principle – Shirly Geffen Apr 11 '14 at 9:50
• I have added a step, hope it's clear enough now. – gar Apr 11 '14 at 10:31
• @gar: Thanks, it's clear now -- before you edited your answer I'd started writing one, and arrived at the same answer independently. +1. – ShreevatsaR Apr 11 '14 at 10:51

Your original approach is fine: we want the coefficient of $x^{3000}$ in

$$(x^{500} + x^{501} + \dots + x^{2000}) (x^{150} + x^{151} + \dots + x^{1000})^4$$ $$= x^{500 + 150\times 4}(1 + x^2 + \dots + x^{1500})(1 + x + \dots + x^{850})^4$$ $$= x^{1100}\frac{1-x^{1501}}{1-x} \left(\frac{1-x^{851}}{1-x}\right)^4$$

The coefficient of $x^{3000}$ in the above is \begin{align} &[x^{3000}]x^{1100} (1-x^{1501})(1-x^{851})^4(1-x)^{-5} \\ &= [x^{1900}]\left((1-x^{851})^4(1-x)^{-5}\right) - [x^{399}]\left((1-x^{851})^4(1-x)^{-5}\right) \tag 1 \end{align}

Now, we have from the binomial theorem, $$(1-x^{851})^4 = 1 - \binom{4}{1}x^{851} + \binom{4}{2}x^{851\times2} + \dots$$ and $$(1-x)^{-5} = 1 + \binom54x + \binom64x^2 + \binom74x^3 + \dots + \binom{k+4}{4}x^k + \dots$$

So the two coefficients in $(1)$ are, respectively, \begin{align} & [x^{1900}]\left((1-x^{851})^4(1-x)^{-5}\right) \\ &= [x^{1900}](1-x)^{-5} - \binom41 [x^{1900-851}](1-x)^{-5} + \binom42[x^{1900-851\times2}](1-x)^{-5} \\ &= \binom{1900 + 4}{4} - \binom41 \binom{1049 + 4}{4} + \binom42 \binom{198 + 4}{4} \\ &= 342527319476 \end{align} and $$[x^{399}]\left((1-x^{851})^4(1-x)^{-5}\right) = [x^{399}](1-x)^{-5} = \binom{399 + 4}{4} = 1082740100$$

Thus $(1)$ gives the answer to be $$342527319476 - 1082740100 = 341444579376.$$