Combinatorics
Combinatorics is, in essence, the study of arrangements: pairings and groupings, rankings and orderings, selections and allocations. There are three principal branches in the subject. Enumerative combinatorics is the science of counting. Problems in this subject deal with determining the number of possible arrangements of a set of objects under some particular constraints. Existential combinatorics studies problems concerning the existence of arrangements that possess some specified property. Constructive combinatorics is the design and study of algorithms for creating arrangements with special properties.
We will introduce the basics of counting techniques in this paragraph.
Many counting problems can be classifed as one of the following types:
 Permutations:Count the number of ordered arrangements or ordered selections of objects
 distinct objects only
 repetition of objects
 Combinations:Count the number of unordered arrangements or unordered selections of objects
 distinct objects only
 repetition of objects
Instead of distinguishing between nonrepetition and repetition of objects, we will distinguish between selections from a set and a multiset.
A multiset is like a set except that its members need not be distinct. For example, the sets $\{a,b\}$ and $\{a,a,b\}$ are the same, but the
multisets $\{a,b\}$ and $\{a,a,b\}$ are not the same. We denote a multiset as follows $M=\{x_1.a_2,x_2.a_2,\cdots,x_n.a_n\}$. The numbers $x_1,x_2,\cdots,x_n$ are nonnegative numbers, called repetition numbers.
Counting Principles
Let $S$ be a set. A partition of $S$ is a collection $S_1,S_2,\cdots,S_m$ of subsets of $S$ such that $S_1 \cup S_2 \cup \cdots \cup S_m=S$ and $S_i \cap S_j =\emptyset$ for $i \neq j$. The sets $S_1,S_2,\cdots,S_m$ are pairwise disjoint and there union is $S$. The number of objects, the size or cardinality of $S$ is denoted by $\left{S}\right$.
Addition Principle

Given a set $S$ and a partition $S_1,S_2,\cdots,S_m$ of $S$ then:
\[
\left{S}\right=\left{S_1}\right+\left{S_2}\right+\cdots+\left{S_m}\right
\]
Multiplication Principle

Suppose a set $S$ consists of ordered ntuples, $(x_1,x_2,\cdots,x_n)$ and that there are $a_k$ possible choices for the $k$th element which number does not depend on the specific choices made for the previous elements, then the total number of ntuples in the set is given by:
\[
\left{S}\right=a_1 \times a_2 \times \cdots \times a_n
\]
How many multiples of 5 are there between 10 and 95 ?
For the first digit from the right we have 2 possibilities: 0 or 5. For the second digit from the right we have 9 possibilities. So the total multiple of 5 are 18.
Subtraction principle

Let $S \subset U$, and $S^c$ the complement of $S$ in $U$ then
\[
\left{S}\right=\left{U}\right\left{S^c}\right
\]
Permutations of sets
Given n distinct objects in how many ways can these objects be ordered ?
For the first position $a_1=n$, for the second $a_2=(n1)$, for the last position $a_n=1$, so the total number of orderings of n objects is $n(n1)(n2)....2.1$.
Permutation n objects

A permutation $p(n)$ is the total number of orderings of n distinct objects.
\[
p(n)=n(n1)(n2)...2.1=n!, n\geq 1, p(0)=0!=1
\]
Notice the recursive relation $p(n)=np(n1)$
Given n objects in how many ways can we choose r objects from n ?
This is a slightly different, but related problem. For the first position we have $a_1=n$, for the second $a_2=(n1)$, but the last position is now $a_r=(nr+1)$, so the total number is $n(n1)(n2)....(nr+1)$.
Permutation r objects out of n objects

A permutation $p(n,r)$ is the total number of orderings of r objects selected from n distinct objects.
\[
p(n,r)=n(n1)(n2)....(nr+1)=\frac{n!}{(nr)!}
\]
Combinations of sets
Given n distinct objects in how many ways can we choose r objects from n, but without taking into account order
Let $c(n,r)$ denote this number. The ways to order r objects is $p(r)$. So, each unordered selection can be ordered in p(r) ways. This total must be $p(n,r)$ so we have:
\[
p(r)c(n,r)=p(n,r)
\]
From which follows:
\[
c(n,r)=\frac{p(n,r)}{p(r)}
\]
Combination of r objects out of n distinct objects

A combination $c(n,r)$ is a selection of r objects out of n distinct objects without taking order into account.
\[
c(n,r)=\frac{n!}{r!(nr)!}=\binom{n}{r}
\]
The numbers $\binom{n}{r}$ are called bionomial coefficients for reasons that become clear once we have showed the Binomial Theorem. We have by convention:
\begin{align*"}
\binom{n}{0}=1\\
\binom{n}{r}=0,\: k>n
\\end{align*}
Following propostion shows the symmetry
Proposition

For $0\leq r \leq n$:
\[\binom{n}{r}=\binom{n}{nr}\]

Selecting n objects from r is equivalent to selecting the (nr) objects which shall not be selected.
Q.E.D.
Following proposition is called Pascal's Formula.
Proposition

\[\forall n,k \in \mathbb{N}, \: 1 \leq k < n \]
\[\binom{n}{r}=\binom{n1}{r1}+\binom{n1}{r}\]

Selecting n objects from r is equivalent to number of ways of selecting the nth object and (r1) objects from the remaining (n1) objects plus the number of ways of selecting r objects out of (n1) objects (excluding the nth object).
Q.E.D.
Permutations of multisets
In the arrangements above we assumed n distinct objects. Now we allow a repetition of objects.
Proposition

Let $S$ be a multiset, a set in which members are allowed to appear more than once, with $k$ distinct objects and $n_i$ the number of finite repetition of the ith object. The size of $\left{S}\right=n=n_1+n_2+\cdots+n_k$. The total number of permutations of the elements of $S$ is given by:
\[
\binom{n}{x_1,x_2,\cdots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}
\]

We have $k$ distinct objects, first select the objects $k_1$, this can be done in $\binom{n}{n_1}$ ways. Next choose from the remaining objects the object $k_2$, this can be done in $\binom{nn_1}{n_2}$ ways. We continue selecting the remaining objects in this way and using the product rule we get the following total number of ways of doing that:
\begin{align*}
\binom{n}{n_1}\binom{nn_1}{n_2}\cdots \binom{nn_1n_2\cdots n_{k1}}{n_k} = \\
\frac{n!}{n_1!(nn_1)!}\frac{(nn_1)!}{n_2!(nn_1n_2)!}\cdots\frac{(nn_1n_2\cdots n_{k1})!}{n_k!(nn_1n_2\cdots n_{k})!} =\\
\frac{n!}{n_1!n_2!\cdots n_k!0!} =\\
\frac{n!}{n_1!n_2!\cdots n_k!}
\end{align*}
Q.E.D.
The number
\[\binom{n}{n_1,n_2,\cdots,n_k}\]
is called a multinomial coefficient.
Note:
\[
\binom{n}{n_1,n_2}=\binom{n}{n_1}=\binom{n}{n_2}
\]
Note that above permutation of a multiset is equivalent to the number of ways to partition $n$ distinct objects into $k$ subsets each of lenght $n_k$ with $\sum{n_k}=n$.
Proposition

\[\binom{n}{n_1,n_2,\cdots,n_k}=\binom{n1}{n_11,n_2,\cdots,n_k}+\binom{n1}{n_1,n_21,\cdots,n_k}+\cdots+\binom{n1}{n_1,n_2,\cdots,n_k1} \]

\begin{align*}
\binom{n1}{n_11,n_2,\cdots,n_k}+\binom{n1}{n_1,n_21,\cdots,n_k}+\cdots+\binom{n1}{n_1,n_2,\cdots,n_k1} &= \\
\frac{(n1)!}{(n_11)!n_2!\cdots n_k!}+\frac{(n1)!}{n_1!(n_21)!\cdots n_k!}+\cdots+\frac{(n1)!}{n_1!n_2!\cdots (n_k1)!} &= \\
\frac{n_1(n1)!}{n_1!n_2!\cdots n_k!}+\frac{n_2(n1)!}{n_1!n_2!\cdots n_k!}+\cdots+\frac{n_k(n1)!}{n_1!n_2!\cdots n_k!} &= \\
\frac{(n_1+n_2+\cdots+n_k)(n1)!}{n_1!n_2!\cdots n_k!}&= \\
\frac{n(n1)!}{n_1!n_2!\cdots n_k!} &= \\
\frac{n!}{n_1!n_2!\cdots n_k!} &= \\
\binom{n}{n_1,n_2,\cdots,n_k}
\end{align*}
Q.E.D.
Combinations of multisets
Given a multiset $S$ a $r$combination is an unordered arrangement of $r$ objects of $S$.
Proposition

Let $S$ be a multiset with $k$ different object types each object with a repetition of at least $r$ then the number of $r$combinations of $S$ is:
\[
\binom{r+k1}{r}=\binom{r+k1}{k1}
\]

Let the type of objects be denoted by $a_1,a_2,...,a_k$ so $S=\{r.a_1,r.a_2,\cdots,r.a_k\}$. Any $r$ combination of $S$ is a set of the following form:
$\{x_1a_1,x_2a_2,\cdots,x_ka_k\}$, with $x_1,x_2,\cdots,x_k$ nonnegative integers and $x_1+x_2+\cdots+x_k=r$. So there is a onetoone relation between the number of $r$combinations and the number of solutions of $x_1+x_2+\cdots+x_k=r$. Define the set
\[
T=\{r.1, (k1).0\}
\]
The $(k1)$ symbols $0$ divide the $r$ symbols $1$ into $k$ groups. Let there be $x_1$ symbols $1$ left to the first symbol $0$ and $x_2$ symbols $1$ between the first symbol $0$ and the second $0$, and so on, with $x_k$ symbols $1$ to the right of the last symbol $0$. Each such arrangement is a solution of $x_1+x_2+\cdots+x_k=r$ and thus there is a onetoone relation between the number of these arrangements and the number of $r$ combinations. The total number of these arrangements is the number of permutations of $T$ and is:
\[
\frac{(r+k1)!}{r!(k1)!}=\binom{r+k1}{r}=\binom{r+k1}{k1}
\]
Q.E.D.