Distribute 5 pirates find 3000 gold coins, if the captain gets $\ge 500$ but $\le 2000$ coins, the rest get $\le150$ but $\ge1000$ coins.(each one)

Question

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.

Answer 1

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 $

Answer 2

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