Content

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:

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 non-negative 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 n-tuples, $(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 n-tuples 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=(n-1)$, for the last position $a_n=1$, so the total number of orderings of n objects is $n(n-1)(n-2)....2.1$.

Permutation n objects

A permutation $p(n)$ is the total number of orderings of n distinct objects. \[ p(n)=n(n-1)(n-2)...2.1=n!, n\geq 1, p(0)=0!=1 \]
Notice the recursive relation $p(n)=np(n-1)$

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=(n-1)$, but the last position is now $a_r=(n-r+1)$, so the total number is $n(n-1)(n-2)....(n-r+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(n-1)(n-2)....(n-r+1)=\frac{n!}{(n-r)!} \]

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!(n-r)!}=\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}{n-r}\]

Proof

Following proposition is called Pascal's Formula.

Proposition

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

Proof

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 i-th 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!} \]

Proof

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{n-1}{n_1-1,n_2,\cdots,n_k}+\binom{n-1}{n_1,n_2-1,\cdots,n_k}+\cdots+\binom{n-1}{n_1,n_2,\cdots,n_k-1} \]

Proof

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+k-1}{r}=\binom{r+k-1}{k-1} \]

Proof