5
$\begingroup$

The Android mobile game "Pocket Tanks" has 295 unique weapons. For each match, 20 weapons are inserted into a list. Of those 20, players alternately draw weapons until all are exhausted, leaving each player with 10 weapons.

I'm trying to think of how many combinations of weapons exist. Is this "(295 choose 20) choose 10"? If so this evaluates to an extremely large number. It's large enough that "(295 choose 20) choose 10" in WolframAlpha can't evaluate. You have to calculate the first parenthetical, then evaluate the remaining piece.

$\endgroup$
  • $\begingroup$ Note that $\binom{\binom{295}{20}}{10}$ would be the number of ways to choose $10$ distinct (but otherwise unrelated) lists of $20$ weapons each. That is a large number indeed. $\endgroup$ – Marc van Leeuwen Nov 13 '14 at 12:28
9
$\begingroup$

As you thought, it would actually be $\binom{295}{20} \binom{20}{10}$. This is because you're selecting every combination of 20 and then every configuration of which 10 weapons the first player received.

This can alternatively be represented as a multinomial with three categories.

$$ \binom{n}{k_1, k_2, k_3} $$

$n = $ Total number of weapons $ = 295$
$k_1 = $ Player 1's Weapons $= 10$
$k_2 = $ Player 2's Weapons $= 10$
$k_3 = $ Unused Weapons $= 275$

So, the total number of combinations is

$$ \binom{295}{10, 10, 275} = \frac{295!}{10!\ 10!\ 275!} $$

This is still ludicrous to evaluate, but since it's a division, you can split up some of the work so that Wolfram Alpha doesn't pass out trying to evaluate it.

Edit:

In fact, representing it like this allows Wolfram Alpha to tackle it directly without passing out and gives you a result.

$$ \binom{295}{10, 10, 275} = 979,092,999,029,074,303,631,255,812,346,789,256 $$

Source (Wolfram Alpha link)

$\endgroup$
  • $\begingroup$ What field of math is this? I don't recall learning expressing multinomials in this format? $\endgroup$ – user38537 Nov 13 '14 at 12:03
  • $\begingroup$ The field would be combinatorics, but you may learn combinatorics from numerous different places and classes (such as probability). That is the multinomial coefficient notation. If you don't believe me, Wikipedia $\endgroup$ – Axoren Nov 13 '14 at 12:06
  • $\begingroup$ I've only ever seen n choose k math in subsets. More notably, for the lottery. Finding the possible number of results is fascinating. But I'd never seen the (n/k1, k2, k3) notation before. Thanks for the link. I'll read up on that. $\endgroup$ – user38537 Nov 13 '14 at 12:15
  • $\begingroup$ It's TeX formatting is \binom{n}{k_1, k_2, k_3, ..., k_m}, for future reference. $\endgroup$ – Axoren Nov 13 '14 at 12:17
  • $\begingroup$ Just occurred to me that there can be duplicate weapons in a match, for either player. That's a different question altogether. $\endgroup$ – user38537 Nov 13 '14 at 13:18
4
$\begingroup$

The number of combinations is $$\binom{295}{20}\binom{20}{10}=\frac{295!}{10!10!275!}$$ In the first expression the first factor represents the number of possibilities of choosing $20$ out of $295$. The second factor represents the number of possibilities of choosing $10$ out of $20$.

Note that in the second expression number $20$ is not present (except as summation of $10$ and $10$). This because the 'step in between' of inserting them in a list is somehow irrelevant.

$\endgroup$
  • $\begingroup$ The number 20 is present, in a way, in the number 275. $\endgroup$ – Regret Nov 13 '14 at 11:26
  • $\begingroup$ Yes, but only due to the requirements of a multinomial that every $k_i$ must sum together to equal $n$. $\endgroup$ – Axoren Nov 13 '14 at 11:28
  • 1
    $\begingroup$ Rather, the $10$ and $10$ of the player's weapon counts are more present than the intermediate $20$, so I wouldn't say that $20$ is present at all. $\endgroup$ – Axoren Nov 13 '14 at 11:28
  • 1
    $\begingroup$ I go along with @Axoren. $\endgroup$ – drhab Nov 13 '14 at 11:29
  • 1
    $\begingroup$ I see. 20 is as present as 285 is, only a sum of terms in the factorials. $\endgroup$ – Regret Nov 13 '14 at 11:35
2
$\begingroup$

The number of ways to choose 20 weapons from 295 is $295\choose20$. The number of ways to choose 10 weapons from 20 is $20\choose10$, which is the same number as possible matches given a set of 20 weapons, since 10 weapons go to both players. So the total number of possible matches is ${295\choose20}{20\choose10}$.

$\endgroup$

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.