Combinatorics

Permutations

Factorial notation

$n$ factorial is expressed as $n!$.

$n!$ is defined as follows:

$$n!=n(n-1)(n-2)\dots \left(2\right)\left(1\right)$$

The number of arrangements of a group of $n$ things is $n!$.

Permutations

A permutation can be defined as the total number of ways of picking $r$ things from a group of $n$ things if order matters. This is expressed as ${}^n{P}_r$ or ${}_n{P}_r$. (Generally in this course the former is used.)

$${}^n{P}_r=\frac{n!}{(n-r)!}$$

Multiplication Principle

The multiplication principle states that, if two operations are performed in order with $X$ possible outcomes of the first and $Y$ possible outcomes of the second, then the number of possible outcomes of the first operation followed by the second is equal to $X\cdot Y$.

Addition Principle

The addition principle states that, if there are $X$ ways of performing one operation and $Y$ ways of performing another operation, and it is impossible to perform both operations simultaneously, then there are $X+Y$ ways to perform one operation or the other.

Inclusion-Exclusion

For two possible events, the inclusion-exclusion principle states that the number of ways for one or the other to occur is equal to the number of ways that the first can occur $+$ the number of ways that the second can occur $-$ the number of ways that both can occur.

We can generalise this as follows.

Number of possible outcomes of the combination of a number of sets $=$ the sum of the number of possible outcomes of each set $-$ the sum of the number of possible outcomes of every combination of two events $+$ the sum of the number of possible outcomes of every combination of three events $+\dots$.

To illustrate this more clearly, represent each event as a letter, e.g. $A$. Let the number of outcomes of both of two events be represented by $A\cap B$, and the number of outcomes of either of two events be $A\cup B$. We can now represent inclusion-exclusion as follows:

$$A\cup B\cup C\cup \cdots =(A+B+C+\dots )-(A\cap B+A\cap C+\cdots +B\cap C+B\cap D+\cdots +C\cap D+C\cap E)+(A\cap B\cap C+A\cap B\cap D+\dots )-\dots$$

Example

Q. Find the number of integers between $1$ and $100$ inclusive that are divisible by either $3$, $4$ or $5$.

To solve this, we can use inclusion-exclusion.

The answer will be equal to (the number of integers divisible by $3$ $+$ number of integers divisible by $4$ $+$ number of integers divisible by $5$) $-$ (number of integers divisible by $3$ and $4$ + number of integers divisible by $4$ and $5$ + number of integers divisible by $3$ and $5$) $+$ (number of integers divisible by $3$, $4$ and $5$).

Let the event 'divisible by 3' be $A$, the event 'divisible by 4' be $B$ and 'divisible by 5' be $C$. Then we can express the above as:

$$A\cup B\cup C=(A+B+C)-(A\cap B+A\cap C+B\cap C)+(A\cap B\cap C)$$

Now we calculate each of $A$, $B$, $C$, $A\cap B$, $A\cap C$, and so on.

$$A=\lfloor \frac{100}{3}\rfloor =33B=\lfloor \frac{100}{4}\rfloor =25C=\lfloor \frac{100}{5}\rfloor =20A\cap B=\lfloor \frac{100}{12}\rfloor =8A\cap C=\lfloor \frac{100}{15}\rfloor =6B\cap C=\lfloor \frac{100}{20}\rfloor =5A\cap B\cap C=\lfloor \frac{100}{60}\rfloor =1$$

So the answer can be calculated as:

$$(33+25+20)-(8+6+5)+\left(1\right)=60$$

Pigeonhole Principle

The pigeonhole principle, in its most basic form, states:

If there are $n$ pigeons and less than $n$ pigeonholes, there must be at least one pigeonhole containing more than one pigeon.

We can extend this:

If there are $n$ pigeons and $k$ pigeonholes, there is at least one hole containing at least $\lceil \frac{n}{k}\rceil$ pigeons.

Combinations

Combinations are similar to permutations except they do not differentiate based on order. Combinations are written using one of the formats $(\frac{n}{r})$ or ${}^n{C}_r$.

$$(\frac{n}{r})=\frac{n!}{r!(n-r)!}=\frac{{}^n{P}_r}{r!}$$