# 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.^{[1]} 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_{1}*n*are the total number of each type of objects within the group._{r}

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 *p*'s, 2 *e*'s, 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.

## References

- ↑ Ross, Sheldon. "A First Course in Probability 7e". Pearson Education: 2006.