Most gambling games are well understood mathematically, and are rigged so that the house has a small advantage. Casino customers play games for entertainment, and rely on luck. Casinos host the games to make money, and rely on mathematics to succeed.
These gambling games, and many other practical concerns, are discussed in terms of probabilities. To understand probabilities, one needs to know how to count certain kinds of events. It is convenient to speak in terms of various familiar activities of selecting items from a set, where the event would be the result of a certain kind of selection. In games, the items might be cards or throws of a die, but the principles are very general, and applicable to many situations and kinds of items.
There are formulas for counting these events. To understand them fully, and to use them, it is helpful to understand how the formulas are derived, because the derivations provide crucial insight into the kind of thinking that can be applied to such problems.
Here are derivations for three of the most important formulas. The first is conceptually the hardest, but the other two follow easily.
One of the most basic ways to select items from a set is to replace the item each time one is chosen.
A simple example would be n distinct balls in an opaque bag. One at a time, a ball is drawn from the bag, noted, and returned.
Each draw is the same: there are n balls, so simply n ways for a ball to be chosen.
For each way to choose a first ball, there are n ways to draw it and then a second ball, so the number of ways to draw two balls is n × n.
Repeating this process k times yields the number of ways to draw k balls from the n in the bag as
A permutation of distinct items is an ordering, or sequence, of the items.
For instance
a, b, c
and
c, a, b
are two different permutations of the letters a, b, and c.
The number of permutations of n items is written symbolically as P(n) .
| a | b | c |
| a | c | b |
| b | a | c |
| b | c | a |
| c | a | b |
| c | b | a |
How many permutations of
| 1 item? | 1 |
| 2 items? | 2 (note this is 2 × 1) |
| 3 items? | 6 (note this is 3 × 2 × 1) |
You might guess that, in general, the number of permutations of n items would be given by the formula
This special product is called n factorial, and it is written
How would one argue that this formula is correct, though?
Suppose you count all the ways to arrange n−1 items, and call it P(n−1). Can you then find a formula for n items based on that?
| d | a | b | c |
| a | d | b | c |
| a | b | d | c |
| a | b | c | d |
Consider how to insert another item into each of these arrangements of n−1 items. For each arrangement, another item could be inserted in any of n positions: before the first, between the first and second, etc., and after the last.
So the number of ways to arrange n items is
That is,
If the formula holds for n−1 items, then the formula for n items is
It follows by the principle of “mathematical induction” that the formula
holds for each n.
Now consider the different arrangements or orderings of k items, taken from n items.
This is the number of ways to choose k items from n distinct items, where the order of the items matters. It is often written
and read “permutations of n items taken k at a time”.
Suppose k items are pulled out of a bag of n items. Then there are n−k items remaining in the bag.
Now, the number of ways to pull out the remaining items is just the number of permutations of the remaining items, P(n−k) .
For each of the P(n, k) ways to pull out the first k items, there are P(n−k) ways to pull out the remaining items. This is P(n, k) × P(n−k) altogether.
But the number of ways to pull out k items, then pull out the remaining n−k, is the same as the number of ways to pull out all n items, which is to say,
Now apply the formula for P(n):
and rearrange to get
The phrase “combinations of n distinct items taken k at a time” means the ways in which k of the n items can be combined, regardless of order.
So rather than considering the orders in which items are chosen, as with permutations, the combinations consider which sets of items are chosen.
The combinations of n distinct items taken k at a time is often written
or
| ( | n | ) |
| k |
The C in C(n, k) stands for “combinations” or “choices”. The number C(n, k) is also often read “n choose k”.
To derive a formula for C(n, k), separate the issue of the order in which the items are chosen, from the issue of which items are chosen, as follows.
The number of permutations of k items taken from n items is
That is to say:
Rearrange this to get:
| C(n, k) | = P(n, k) ⁄ P(k, k) |
| = ( n! ⁄ (n−k)! ) ⁄ k! | |
| = n! ⁄ (k! (n−k)! ) , |
and that is your “binomial coefficient”
While the above expression for the binomial coefficient is convenient to write, it is a very poor way to calculate the value, because most of the factors cancel out in the division.
To calculate, say, C(10, 3), first note that
consists of just the largest 3 factors of 10!
all the other terms cancel. So
The binomial coefficient always turns out to be a whole number, so all the factors of the denominator will cancel with factors in the numerator.