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 $$n_1$$ ways to do the first task and for each of these ways of doing the first task, there are $$n_2$$ ways to do the second task, then there are $$n_1\times n_2 $$ ways to do the procedure. In Set Theory this is known as the Cartesian Product (or dot-product).
$$! \left|N_1 \times N_2 \right| = \left|N_1\right| \bullet \left|N_2\right| $$
Sum Rule
If a task can be done either in one of $$n_1$$ ways or in one of $$n_2$$ ways, where none of the set of $$n_1$$ ways is the same as any of the set of $$n_2$$ ways, then there are $$n_1+n_2$$ 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.
$$! \left| N_1 \cup N_2 \right| = \left| N_1 \right| + \left| N_2 \right| $$
Inclusion-Exclusion Principle
This principle deals with overlapping sets, suppose there are some objects which meet criteria $$n_1$$, some which meet criteria $$n_2$$ and some which meet both $$n_{1\mbox{ and } 2}$$. The total number of all the elements will be $$n_1+n_2-n_{1\mbox{ and } 2}$$. In Set Theory we have:
$$! \left| N_1 \cup N_2 \right| = \left| N_1 \right| + \left| N_2 \right| – \left| N_1 \cap N_2 \right| $$
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:
$$! \mathop P\nolimits_r^n = P(n,r) = \frac{{n!}}{{\left( {n – r} \right)!}} $$
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:
$$!
\mathop C\nolimits_r^n = C(n,r) = \left( {\begin{array}{*{20}c}
n \\
r \\
\end{array}} \right) = \frac{{n!}}{{r!\left( {n – r} \right)!}} $$
Rules Involving Combinations
Binomial Theorum
This theory allows the expansion of polynomial factors:
$$!
\left(x + y\right)^n = \left( {\begin{array}{*{20}c}
n \\ 0 \\
\end{array}} \right)x^n + \left( {\begin{array}{*{20}c}
n \\ 1 \\
\end{array}} \right)x^{n – 1} y + \left( {\begin{array}{*{20}c}
n \\ 2 \\
\end{array}} \right)x^{n – 2} y^2 \ldots + \left( {\begin{array}{*{20}c}
n \\ n – 1 \\
\end{array}} \right)xy^{n – 1} + \left( {\begin{array}{*{20}c}
n \\ n \\
\end{array}} \right)y^n
$$
Pascal’s Identity
This theory allows for the manipulation of combinations.
$$\left( {\begin{array}{*{20}c}
{n + 1} \\ k \\
\end{array}} \right) = \left( {\begin{array}{*{20}c}
n \\ k – 1\\
\end{array}} \right) + \left( {\begin{array}{*{20}c}
n \\ k \\
\end{array}} \right) $$
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
