When distributing these bullets, each burglar must at least have three bullets, but no more than eight.

I have tried solving this with generating functions, but I am stuck at this part where I am not sure what type of "trick" to use to continue on..

My work (incomplete):

The generating function for this problem is $$f(x) = (x^3 + x^4 + ....+ x^8)^4$$ where we seek the coefficient of


$$=(x^3+x^4...+x^8)^4$$ $$=x^(12)( 1 + x+ x^2 + x^3 +x^4 +x^5)^4$$

and using the identities we get that the coefficient of x^12 is

(1-x^6)^4 * (1 - x)^-4

this of course is equal to :

[1-4C1(x^6) + 4C2(x^12) - 4C3(x^18) + x^23] * [-4C0 + -4C1(-x) +.......]

At this point I am totally stuck because this is a huge expansion... and the answer is 125. Is there a method I can use to quickly arrive at the answer or do I have to expand everything in?

  • 1
    $\begingroup$ Are the burglars being armed with these bullets or being shot by them? $\endgroup$ – user856 Jan 31 '15 at 21:39
  • $\begingroup$ If the latter, then I think this would be considered pre-meditation. $\endgroup$ – PepperSausage Jan 31 '15 at 22:45

First, give each burglar $3$ bullets. Then you end up distributing $12$ bullets to $4$ burglars such that no burglar has more than $5$. Think about the four distinguishable burglars as boxes labelled $1,2,3,4$ and the bullets as balls.

Then you have to count the number of nonnegative solutions to $x_1+x_2+x_3+x_4=12$ where $x_i\leqslant 5$. This is the coefficient of $x^{12}$ in $(1+x+x^2+x^3+x^4+x^5)^{4}$. Write this as $$f(x)=(1-x^6)^{4}(1-x)^{-4}$$

Now $$(1-x^6)^{4}=\sum_{\nu\geqslant 0}\binom{4}\nu (-1)^\nu x^{6\nu}=\sum_{\nu\geqslant 0}\binom{4}{\nu/6}(-1)^{\nu/6}[6\mid \nu]x^{\nu}=\sum_{\nu\geqslant 0}a_\nu x^\nu $$

$$(1-x)^{-4}=\sum_{\nu\geqslant 0}\binom{\nu+3}\nu x^{\nu}=\sum_{\nu\geqslant 0}b_\nu x^\nu$$

Then you want $$[x^{12}]f(x)=\sum_{\nu+\mu=12}a_\nu b_\nu=\sum_{\nu+\mu=12}\binom{\nu+3}\nu \binom{4}{\mu/6}(-1)^{\mu/6}[6\mid \mu]\\= \binom{15}{12}\binom 40-\binom 96\binom41+\binom 30\binom 42=125$$

| cite | improve this answer | |

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.