1
$\begingroup$

In a combination problem I can think of three relevant numbers:

i, the number of slots

v, the number of valid values you can put in each slot

k, the number of occurrences of one particular valid value of interest in all slots (e.g., three slots that display the value 'A')

Which one of these goes on top of the binomial coefficient and which one on the bottom? And why is the third number irrelevant?

And when you calculate a probability, by what combination do you divide?

copy/paste from my comment below: ex.:
5 slots, 2 possibilities for each slot (A or B), you're interested in the number of combinations where there are 3 A's (and, hence, 5-3 = 2 B's). like a best 3 of 5 tennis game with players A and B, and you want to know the probability of A winning 3 games if they are evenly matched. but i am going for a more general interpretation in order to understand how i can apply it to counting problems.

  • 1
    You might be i$n$terested in what Wikipedia calls the [Twelvefold way](http://en.wikipedia.org/wiki/Twelvefold_way)2012-08-31

2 Answers 2

0

The number of slots, $i$ goes upstairs, the number of occurrences $k$ goes downstairs, and $v=2$ if you are dealing with a combinations problem. So $\binom ik$ is the number of solutions for having $k$ times a particular values in one slot, among $i$ slots in all, with $2$ possibilities per slot.

If you want more possibilities per slot, you cannot directly use binomial coefficients, but need multinomial coefficients (the "bi" corresponds to $v=2$). You'll notice in this case that just giving the frequency $k$ of one value does not yet well describe the situation; you should specify the frequencies of at least $v-1$ values (the remaining value will take the remainder left from $i$). In practice for multinomial coefficients one specifies the frequencies of all $v$ values, creating a bit of redundancy but giving a more readable result.

2

Suppose you have $n$ distinguishable items and want to choose $k$ of them. This can be done in $\binom{n}{k}$ ways (this number is often called a binomial coefficient). Using your language, there are $k$ unordered slots and $n$ different items to put in the slots. The third idea, that a particular item can be repeated, is sometimes called a combination with repetition. Such combinations are not handled directly by binomial coefficients, but there is an easy formula using them (see the link).

When using combinations to calculate a probability, you want to calculate $ \frac{\text{Successful Combinations}}{\text{Total Combinations}}. $

For example, suppose there are five different beers on the table and you grab three at random. What is the probability that you grab the Guinness as one of your three beers? A successful combination is one including the Guinness, of which there are $\binom{4}{2}$ (grab the Guinness first, then any $2$ of the remaining $4$). The total number of combinations is $\binom{5}{3}$. The probability of getting a Guinness is therefore $ \frac{\binom{4}{2}}{\binom{5}{3}} = \frac{6}{10} = 60\%. $