1
$\begingroup$

This question is inspired by a particular mission in the game World of Tanks. In the game there are 5 tank types (say ${L,M,H,D,A}$). To complete the mission it is necessary that out of 3 tanks (on the enemy team), 2 or more are of type $H$. Using the multinomial number, there are $$ {5+3-1 \choose{3}}=35$$

ways to choose 3 tanks out of 5 when order doesn't matter and with repetition. Manual computation shows that of these, there are 5 selections satisfying the criteria that 2 or more are of type $H$. These are:

$$\{H,H,H\},\{H,H,L\},\{H,H,M\},\{H,H,D\},\{H,H,A\}$$

Clearly we're dividing the $35/7=5$, but where does the $7$ come from?

This got me thinking about the general case: How many ways can we make $k$ unordered selections with repetition from objects of $n$ distinct types such that $0 \leq m \leq k $ or more of the selections are of the same type? What would be a good counting argument for this?

$\endgroup$
1
$\begingroup$

If you just require at least a certain number of some type or types, since order doesn't matter you can just take the minimum number of those first. Then you can calculate the number of ways to choose the remaining objects using the formula you have above. In your example you first take two Hs and then there are five choices for the third tank (including another H).

So if you want to choose $7$ objects of $5$ types there are $\binom{7+5-1}{7}$ ways, but if you require at least one of type A and two of type B, set those aside first and there are $\binom{4+5-1}{4}$ ways to choose the remaining $4$.

$\endgroup$
  • $\begingroup$ Got it: there are 5 selections since there is precisely 1 way to choose two H, leaving only 1 spot left to fill in ${5+1-1 \choose 1}=5$ ways. What if instead of "out of 3 tanks, 2 or more are of type H " we had to find out how many selections satisfied "out of 3 tanks, 2 or more are of any single type?" My guess is we choose 1 type in ${5 \choose 1}$ ways, choose 2 of these in 1 way, then have 5 choices left for the final slot. $\endgroup$ – Evan Rosica May 20 '17 at 14:23
  • $\begingroup$ .... giving 25 total selections. $\endgroup$ – Evan Rosica May 20 '17 at 14:28

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.