# There are five boxes consisting of several identical coins.

There are five boxes consisting of several identical coins. The first box contains 4 coins, the second box contains 9 coins, the third box contains 7 coins, the fourth box contains 10 coins, and the fifth box contains 3 coins. Some coins are taken from the boxes such that at least a coin taken from each box. In how many ways in taking the coins, such that the numbers of the coins taken are 12?

My attempt was solving it using repetition combination of which, there are only seven coins remaining considering that at least a coin taken from each box. By using the repetition combination, i.e. taking 7 from 9 (five boxes and four borders), resulting in 36 ways. However, there is no 36 ways in the choices.

• Note that you cannot take all seven of the extra coins beyond the initial one coin from each from the fifth box... there were only three coins available to take. – JMoravitz Mar 9 at 12:52
• Are you familiar with stars and bars? – Fimpellizieri Mar 9 at 12:54
• @Fimpellizieri clearly, yes (whether or not the OP calls it that), as evidenced by the OP saying "five boxes and four borders." That was not the source of the OP's mistake. The mistake was in that some of the outcomes the OP counted were some outcomes which are impossible due to the limited number of coins available in certain boxes. – JMoravitz Mar 9 at 12:55
• @Fimpellizieri, yes, now I just realized my fault by seeing the comment of Jmoravitz. – wawar05 Mar 9 at 12:57
• If you're not doing formal power series, there is a modification one can apply to stars and bars when dealing with this kind of question, where the variables have both a lower and an upper limit. It uses the principle of inclusion-exclusion, and is a bit of work, but produces closed formulas. This answer explains it. – Fimpellizieri Mar 9 at 13:00

You will need to find the coefficient of $$x^{12}$$ in the series $$(x+x^2+x^3+x^4)(x+x^2+x^3+...+x^9)(x+x^2+x^3+...+x^7)(x+x^2+x^3+...+x^{10})(x+x^2+x^3)$$

i.e. the coefficient of $$x^{7}$$ in the series $$(1+x+x^2+x^3)(1+x+x^2+x^3+...+x^8)(1+x+x^2+x^3+...+x^6)(1+x+x^2+x^3+...+x^8)(1+x+x^2)$$

which can be further simplified to the coefficient of $$x^{7}$$ in the series $$(1-x^4)(1-x^9)(1-x^7)(1-x^{10})(1-x^3)(1-x)^{-5}$$

Well, it can be furthur simplified leaving all the power greater than 7 and power of sevel itself will cancel. $$(1-x^3-x^4...)(1-x)^{-5}$$

=$$C(5+7-1,5-1)-C(5+4-1,5-1)-C(5+3-1,5-1)$$

=$$C(11,4)-C(8,4)-C(7,4)$$

• why there is no series for the fifth box? – wawar05 Mar 9 at 13:00
• You are missing the fifth box. There is also the question of if leaving the answer in this form is acceptable in whatever context the OP is working. I can see arguments both for and against this. If we were to assume the OP has a simple calculator and was required to give a numerical answer, this doesn't help that much. It isn't wrong per se however, and is arguably just as simplified as a solution as one that leaves things as unsimplified binomial coefficients... – JMoravitz Mar 9 at 13:02
• Thanks! Changed it. I missed it while solving – Mathsmerizing Mar 9 at 13:03
• When converting to binomial coefficients, you seem to have made a mistake, namely with the second term, these should each have been $5-1$ rather than $5$. – JMoravitz Mar 9 at 13:20
• Thanks! yeah it should be n-1. :) i always seem to goof up formula – Mathsmerizing Mar 9 at 13:23

Num available: 4,9,7,10,3 - Num needed to take: 12

Take one from each box ahead of time to handle the condition that we need to take at least one from every box

Num available: 3,8,6,9,2 - Num needed to take: 7

Now... if we were to ignore the upper limits on each box, the number of ways to take 7 objects from 5 boxes would be:

$$\binom{7+5-1}{5-1}=330$$

You said something about $$36$$, which implies to me that you have made a mistake or learned stars and bars incorrectly. With $$k$$ distinct boxes and $$n$$ identical balls there are $$\binom{n+k-1}{k-1}$$ ways to place the balls in the boxes (or as in our case, remove balls from the boxes/coins who have an unlimited supply)

Of these outcomes however, you counted some impossibilities, such as where you took too many coins from the first box, so let us remove those impossibilities. If we took too many from the first box, that means we took at least four more from the first box, putting us at the situation of:

Num available: -1, 8,6,9,2 - Num needed to take: 3

Still five boxes, and needing to take only three more, there are $$\binom{3+5-1}{5-1}=\binom{7}{4}=35$$ bad outcomes where we took too many coins from the first box. We similarly count how many bad outcomes there were for having taken too many from the third or fifth box.

Note however, that in counting the number of bad outcomes as a result of taking too many from the first box and counting the number of bad outcomes as a result of taking too many from the fifth box, we accidentally counted one of these outcomes twice... the one where we took too many from both the first and fifth box simultaneously. Correctly applying inclusion-exclusion then we arrive at a final answer of:

$$\binom{7+5-1}{5-1}-\binom{3+5-1}{5-1}-\binom{0+5-1}{5-1}-\binom{4+5-1}{5-1}+\binom{0+5-1}{5-1}$$

$$= \binom{11}{4}-\binom{7}{4}-\binom{4}{4}-\binom{8}{4}+\binom{4}{4} = 225$$

After taking one coin out of each box the boxes have contents $$2,3,6,8,9$$, and we have to pick $$7$$ more coins. From the first box we can take $$0,1,2$$ coins, and from the second box $$0,1,2,3$$ coins. This gives $$1,2,3,3,2,1$$ ways to take $$0,1,2,3,4,5$$ coins from these two boxes. The remaining $$7,6,5,4,3,2$$ coins to pick can be taken arbitrarily from the three other boxes, with one exception: you cannot take all $$7$$ coins from the $$6$$-coins box. Using stars and bars for these pickings we therefore obtain the following total number of admissible cases: $$N=1\cdot\left({9\choose2}-1\right)+2\cdot{8\choose2}+3\cdot{7\choose2}+3\cdot{6\choose2}+2\cdot{5\choose2}+1\cdot{4\choose2}=225\ .$$