Combinatorics

Combinatorics is a field of mathematics devoted to the study of counting elements in a set, and mathematical relations that describe their properties. This field is "discrete", meaning it deals with non-continuous properties. Combinatorics is very useful in the field of discrete probability theory.

Combinatorial Functions

Many functions used in combinatorics deal with how to count or arrange numbers. These rules are all based on the basic principle of counting, which states that for any two groups of objects of size m and n, there are m • n possible combinations. For example, If you have 10 different marbles and 8 different cups, there are 80 (10 • 8) ways to put a marble into a cup.

Permutations

A permutation is a certain way to order a group of objects. For example, bac is one permutations of the letters a, b, and c. For three objects it is easy to see that there are 6 total permutations by simply writing out all of the combinations (abc, acb, bac, bca, cab, and cba).

For larger groups of objects it is harder, if not impossible, to write out all combinations. However a simple formula can be derived from the basic principle of counting, which states that, for a group of n objects, there are n! ("n factorial") possible ways to order those objects. So for our above example, we can calculate that there are 6 possible ways (3 • 2 • 1) to order three objects.

For groups of indistinguishable objects, you must divide the total number of redundant ways to permute the objects:

, where n is the total number of objects, and n₁ through n_r are the total number of each type of objects within the group.

For example, the letters p and e in the word "pepper" are indistinguishable from one another. There are 6 total letters, which are comprised of 3 ps, 2 es, and 1 r. The total number of permutations would thus be 6! / (3 ! 2! 1!), or 60.

Combinations

It is often useful to find out how many groups of r objects can be created out of a group of n objects. This can be calculated from a function called "choose" (read aloud as "n choose r"):

For example, take a race which has 10 competitors. There are 10 choose 3 different combinations of medal winners (that is, racers who get either 1st, 2nd, or 3rd place), which is a total of 10! / (10 - 3)! • 3! = 10! / 7! • 3! = 120 different combinations.

The numbers are also called binomial coefficients because of the binomial expansion: