Powered by MathJax
We use MathJax

Basic Counting

Combinatorics is the study of counting the number of ways events can happen.  Since such results are often quite large, we do not want to list all of the possibilities and count them one by one.  Combinatorics will provide various rules and formulas for more quickly determining results.

Stages and the Multiplication Rule

Suppose an event comes in two stages.  The number of ways the first stage can occur is the number $m$, and the number of ways the second stage can occur is $n$.  Then the event consisting of the two stages together can occur in $mn$ ways.

Tree diagram of the problem

The Multiplication Rule can be generalized to any number of stages.

Sometimes the stages appear to be identical, but each stage should be considered distinct.

And sometimes the choices in each stage are "yes" and "no", whether a particular item is included or not.

There is always a certain assumption of order in the Multiplication Rule.  In each of the examples above, there was a first stage to the event, and a second stage, and so on.

Arrangements and the Permutation Rule

A permutation is an arrangement of a set of objects.  A set of $n$ objects can be arranged in $n!$ ways.  The Permutation Rule is a special case of the Multiplication Rule, where the each stage of a decision always has one less possibility than the previous stage.

Arrangements are usually assumed to be linear, and the line has an order (a front of the line, and a back of the line).  If there is no front or back, but only a center of the arrangement, the Permutation Rule result will have to be divided by the number of rotational symmetries in the arrangement.  (If the distinction between left and right is also ignored, then the denominator will be twice as large.)

Distinguishable Permutations and the Multinomial Coefficient

When the set contains some objects that are identical (or at least indistinguishable according to a certain characteristic), then the number of permutations must be divided by the number of ways the identical objects could be arranged.  In other words, if a set has $n$ objects of $k$ different types, with $n_1$ of the first type, $n_2$ of the second type, etc., then there are   $\dbinom{n}{n_1,n_2,\ldots,n_k}=\dfrac{n!}{n_1!\times n_2!\times\ldots\times n_k!}$   distinguishable permutations of that set.

Permutations of a Subset

Sometimes only the first few items in the arrangement are important, and the rest can be ignored.  That is, the number of permutations of $n$ objects taken $r$ at a time is   ${}_n P_r = \dfrac{n!}{(n-r)!}$.   This is really a special case of the Distinguishable Permutation Rule.

Choices and the Combination Rule

When items are selected or chosen from a set, essentially two groups are being identified.  One group consists of those items chosen, and the other group are the items not chosen.  When the order of the items chosen is irrelevant, the selection is called a combination.  There are   ${}_n C_r = \dbinom{n}{r} = \dfrac{n!}{r!(n-r)!}$   combinations of $n$ objects taken $r$ at a time.  This result is also a special case of the Distinguishable Permutation Rule.