Theory

Theory 1

In many “games of chance”, it is assumed by symmetry principles that all outcomes are equally likely. From this assumption we infer the rule for :

In words: the probability of event is the number of outcomes in divided by the number of possible outcomes.

When this formula applies, it is important to be able to count total outcomes, as well as outcomes satisfying various conditions.

Permutations

Permutations count the number of ordered lists one can form from some items. For a list of items taken from a total collection of , the number of permutations is:

To see where this comes from: There are choices for the first item, then for the second, then … then for the item. So the number is . Observe:

Combinations, binomial coefficient

Combinations count the number of sets (ignoring order) one can form from some items. We define a notation for it like this:

This counts the number of sets of distinct elements taken from a total collection of items.

Another name for combinations is the binomial coefficient.

This formula can be derived from the formula for permutations. The possible permutations can be partitioned into combinations: each combination gives a set, and by specifying an ordering of elements in the set, we get a permutation. For a set of elements taken from items, there are ways to put them into a specific order. So the number of permutations must be a factor of greater than the number of combinations.

This notation, , is also called the binomial coefficient because it provides the coefficients of a binomial expansion:

For example:

There are also ‘higher’ combinations:

Multinomial coefficient

The general multinomial coefficient is defined by the formula:

where and .

The multinomial coefficient measures the number of ways to partition items into sets with sizes , respectively.

Notice that so we already defined these values with binomial coefficients. But with , we have new values. They correspond to the coefficients in multinomial expansions. For example gives coefficients for .