Combinatorics
Combinatorics is a branch of mathematics concerned with the study of finite objects, and has many applications in the field of Computer Science. Combinatorics is useful in problem solving, and is most often involves ideas such as counting elements in a set, or calculating permutations or combinations of elements in a set.
Counting Principles
Product Rule
Suppose that a procedure can be broken down into a sequence of two tasks. If there are 
ways to do the first task and for each of these ways of doing the first task, there are 
ways to do the second task, then there are 
ways to do the procedure. In Set Theory this is known as the Cartesian Product (or dot-product).
Sum Rule
If a task can be done either in one of ways or in one of ways, where none of the set of ways is the same as any of the set of ways, then there are 
ways to do the task. In Set Theory we say that the union of the two disjoint sets contains the total number of elements from both sets.
Inclusion-Exclusion Principle
This principle deals with overlapping sets, suppose there are some objects which meet criteria , some which meet criteria and some which meet both 
. The total number of all the elements will be 
. In Set Theory we have:
Permutations and Combinations
A permutation is an ordered set of distinct objects. If a permutation of a set must contain all items in the set then the number of possible permutations is n! where ! denotes factorial. We can however have an ordered permutation of a set with r objects, known as a r-permutation, the formula for calculating the number of permutations for this is shown below:
If we do not want to consider the permutations as ordered, but rather ordered, then we instead refer to the results as combinations not permutations. Thus, an r-combination of a set is simply a subset of the set with r elements. The number of possible r-combinations is called a binomial co-efficient, and can be calculated as shown below:
Rules Involving Combinations
Binomial Theorum
This theory allows the expansion of polynomial factors:
Pascal's Identity
This theory allows for the manipulation of combinations.
References:
- FA-ADM - Slides 5 - University of Durham - Ioannis Ivrissimtzis - 2007
- FA-ADM - Slides 6 - University of Durham - Ioannis Ivrissimtzis - 2007
- Discrete Mathematics and Its Applications - Sixth Edition - Kenneth H. Rosen
- Combinatorics - Wikipedia - http://en.wikipedia.org/wiki/Combinatorics