1. Combinatorics

The Multiplication Principle for Counting Procedures

If a sequence can be described as a sequence of $n$ independent steps, with $i_{1}$ possible outcomes for the first step, $i_{2}$ possible outcomes for the second step, $\dots$ , and $i_{n}$ possible outcomes for the $n^{t h}$ step, then the total number of composite outcomes of the procedure is $i_{1} i_{2} \dots i_{n}$

The Addition Principle for Counting Procedures

If a procedure can be broken up into $m$ events or cases whose sets of outcomes are mutually exclusive, with $j_{1}$ possible outcomes for the first event, $j_{2}$ possible outcomes for the second event, $\dots$ , and $j_{m}$ for the $m^{t h}$ event, then the total number of outcomes of the procedure is $j_{1} + j_{2} + \dots + j_{m}$

Suppose that a child is offered a bag containing three types of sweets, aniseed drops $(A)$ , butter mints $(B)$ and cherry drops $(C)$ . In how many ways can the child select two sweets?

This problem is not defined well, since we are not told:

whether or not the same type of sweet can be selected twice, i.e. is $A A$ allowed?
whether the order matter, i.e. is $A B$ to be treated the same as $B A$ , or not?

There are 4 cases to consider:

Repeats are allowed and order matters. This gives 9 possibilities:
- $A A, A B, A C, B A, B B, B C, C A, C B, C C$
- Permutations with Unlimited Repetition
Repeats are allowed and order doesn’t matter. This gives 6 possibilities:
- $A A, A B, A C, B B, B C, C C$
- Combinations with Unlimited Repetition
Repeats are not allowed and order matters. This gives 6 possibilities
- $A B, A C, B A, B C, C A, C B$
- Permutations
Repeats are not allowed and order doesn’t matter. This give 3 possibilities
- $A B, A C, B C$
- Combinations

At first glance the expression $(a + b)^{n}$ does not have much to do with Combinations, but it turns out that we can obtain the formula for the expansion of $(a + b)^{n}$ by using the formula for $k$ -combinations of $n$ objects

$\begin{aligned} (a + b)^{3} \\ = (a + b) (a + b) (a + b) \\ = a a a + a a b + a b a + a b b + b a a + b a b + b b a + b b b \\ = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3} \end{aligned}$
Theorem 1.5

If $a$ and $b$ are real numbers and $n$ is a positive integer, then $(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k}$

Proof: $(a + b)^{n} = (a + b) \dots (a + b) (n factors)$

In the expansion of $(a + b)^{n}$ , a term of the form $a^{n - k} b^{k}$ arises from choosing $b$ from $k$ factors and $a$ from the other $n - k$ factors. This can be done in $(\binom{n}{k})$ ways. Thus $a^{n - k} b^{k}$ appears $(\binom{n}{k})$ times in the expansion. It follows that:
$\begin{aligned} (a + b)^{n} \\ = (\binom{n}{0}) a^{n - 1} b^{1} + (\binom{n}{2}) a^{n - 2} b^{2} + \dots + (\binom{n}{n - 1}) a^{1} b^{n - 1} + (\binom{n}{n}) a^{0} b^{n} \\ = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k} \end{aligned}$
The numbers $(\binom{n}{k})$ are known as binomial coefficients because they appear in the expansion of $(a + b)^{n}$

Example

What is the coefficient of $x^{12} y^{13}$ in the expansion of $(x + y)^{25}$

$(\binom{25}{13}) = \frac{25!}{13! 12!}$

Example

Find the coefficient of $x^{4} y^{5}$ in the expansion of $(2 x - y)^{9}$

$(- 1)^{5} \times (\binom{9}{5}) \times 2^{4} = - 2016$

Example

Find the coefficient of $x^{2} y^{3} z^{4}$ in the expansion of $(x + y + z)^{9}$

Model as $(x + (y + z))^{9}$
$(\binom{9}{7}) (y + z)^{7}$
$= (\binom{9}{7}) (\binom{7}{4}) = 1260$

Example

Prove that for a positive integer $n$ , $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$

Proof using the Binomial Theorem
$2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 1^{n - k} 1^{k} = \sum_{k = 0}^{n} (\binom{n}{k})$

Combinatorial Proof
A set with $n$ elements has $2^{n}$ different subsets
Each subset has $k$ elements for $k \in {0, 1, \dots, n}$
There are $(\binom{n}{k})$ subsets with $k$ elements
Therefore the total number of subsets is $\sum_{k = 0}^{n} (\binom{n}{k})$ ,
and hence $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$

The Pigeonhole Principle (or the Dirichlet Principle) is sometimes useful in answering the question:
Is there an item having a given property?

Pigeonhole Principle: If $n$ pigeons fly into $k$ pigeonholes and $k \leq n$ , then some pigeonhole contains at least two pigeons
Example:

Example

Ten people have the first name Alice, Bernard and Charles, and last names Lee, Mc-Duff and Ng. Show that at least two people have the same first and last names.

There are $3 \times 3 = 9$ possible names for the 10 people. If we think of people as pigeons and the names as pigeonholes, we can consider the assignments of names to people as assigning pigeonholes to pigeons. By the Pigeonhole Principle, some name (pigeonhole) is assigned to at least two people (pigeons)

Generalised Pigeonhole Principle: If $n$ pigeons fly into $k$ pigeonholes, then some pigeonhole contains at least $⌈ \frac{n}{k} ⌉$ pigeons

Proof:

Suppose that none of the pigeonholes contain more than $⌈ \frac{n}{k} ⌉ - 1$ pigeons. Then the total number of pigeons is at most $k (⌈ \frac{n}{k} ⌉ - 1)$ , which is always less than $n$

Example

What is the minimum number of students required in a discrete maths class to be sure that at least 6 will receive the same grade, if there are 5 possible grades, A,B,C,D and F

$⌈ \frac{n}{5} ⌉ = 6$
$n = 5 (6 - 1) + 1 = 25 + 1 = 26$

The Multiplication Principle for Counting Procedures

The Addition Principle for Counting Procedures

Proof: (a+b)n=(a+b)…(a+b) (n factors)

Proof:

Proof: $(a + b)^{n} = (a + b) \dots (a + b) (n factors)$