1. The sum and the inclusion-exclusion principle

The sum

Cardinality

We denote the size, or cardinality, of a finite set $S$ by: $\boxed{|S|}$

Note: $|\varnothing |=0$

For example:

• Let $S=\{a,b,c\}$ hence $|S|=3$. It is said that the cardinality of $S$ is 3, or $S$ has 3 elements.
• If $A=\{n\in \mathbb{N}|n\text{ is an odd number between }4\text{ and }24\}$ then $|A|=10$.

Link to original

The sum rule

The sum rule states that if $A$ and $B$ are disjoint sets then $|A\cup B|=$ $|A| + |B|$.

According to the sum rule, if $A_1,A_2,...,A_n$ are $n$ parwise disjoint sets then $|A_1\cup A_2\cup ...\cup A_n|=$ $|A_1| + |A_2| + ... + |A_n|$.

title: Example
A student can choose one project from project lists of three lecturers.
- John's list has 11.
- Bill's has 10.
- Eve's has 8.
 
No project occurs twice. How many possible projects are there to choose from?
- $A = \{ p | p \text{ is a project on John's list} \}$
- $B = \{ p | p \text{ is a project on Bill's list} \}$
- $C = \{ p | p \text{ is a project on Eve's list} \}$
 
Hence $|A \cup B \cup C| = |A| + |B| + |C| = 29$.

Link to original

Inclusion-exclusion principle

Inclusion-exclusion principle

The inclusion-exclusion principle states that $|A\cup B|=$ $|A| + |B| - |A \cap B|$.

The inclusion-exclusion principle can be applied for three sets, by applying the same rule twice, $|A\cup (B\cup C)|$, giving us: ?

$$\begin{array}{rl}\boxed{|A\cup B\cup C|}& =|A\cup (B\cup C)|\\ & =|A|+|B\cup C|-|A\cap (B\cup C)|\\ & =|A|+|B|+|C|-|B\cap C|-|A\cap (B\cup C)|\\ & =|A|+|B|+|C|-|B\cap C|-|(A\cap B)\cup (A\cap C)|\\ & =|A|+|B|+|C|-|B\cap C|-(|A\cap B|+|A\cap C|-|(A\cap B)\cap (A\cap C)|)\\ & =\boxed{|A|+|B|+|C|-|B\cap C|-|A\cap C|-|A\cap C|+|A\cap B\cap C|}\end{array}$$ Link to original

Link to original

2. The product rule

The product rule

The product rule

If there is a sequence of $k$ tasks such that:

• there are $n_1$ ways to do the first task
• $n_2$ to do the second
• $n_k$ to do the $k$th task ? Then, there are $n_1\cdot n_2\cdot ...\cdot n_k$ ways to do the whole sequence of $k$ tasks

$$|A_1\times A_2\times ...\times A_k|=|A_1|\cdot |A_2|\cdot ...\cdot |A_k|$$

title: Example 1
If each number plate contains a sequence of three letters followed by three digits (and no such sequence is prohibited), then the number of available different number plates is:
 
$$
	26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 17, 576, 000
$$

Usage with functions

If $|A|=n$ and $|B|=m$ then the number of different $f:A\to B$ functions is: ?

$$\stackrel{n}{\overbrace{m\cdot m\cdot ...\cdot m}}=m^n$$

title: Example 2 (with functions)
Let $A = \{ a,b,c \}, B = \{ d,e \} \rightsquigarrow n = 3, m = 2$.
- There are $2$ ways to choose a value for $a$.
Then there are $2$ ways to choose a value for $b$ and then $c$.
 
Hence $2^3 = 8$.

Link to original

Counting the subsets of a finite set

Let $S$ be a finite set having $n$ elements. How many subsets does $S$ have? Or otherwise, what is the cardinality of $P(S)$?

We list the elements of $S:s_1,s_2,...,s_n$. We can choose a subset $A$ of $S$ by going through this list and decide for each element whether it is in $A$ or not.

• We have one ‘task’ for each element: $n$ tasks total
• Each task can be done in two ways: IN or OUT We choose whether to leave it in or leave it out.

Hence, by product rule:

$$|P(S)|=\stackrel{n}{\overbrace{2\cdot 2\cdot ...\cdot 2}}=2^n$$

Combining sum and product rules

Take for example, how many four-digit numbers can begin with either $7$ or $42$?

• The set can be broken down into two disjoint sets:
  1. four-digit numbers beginning with $7$
  2. four-digit numbers beginning with $42$
• In case (1), if we begin with $7$, there are $3$ digits to be filled in with $10$ choices each. Hence by product rule: $10\cdot 10\cdot 10=1000$
• In case (2), there are $2$ digits to be filled with $10$ choices each. So $10\cdot 10=100$.
• Hence by sum rule, we combine these to be $1000+100=1100$.

Link to original

3. The pigeonhole principle

The pigeonhole principle

Pigeonhole principle

If $k\in {\mathbb{N}}^{+}$ and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more objects.

If there are at least $m$ cocks and $n$ holes such that $m>n$, then there must be at least $1$ hole with more than $1$ cock.

Link to original

For example:

• Among any group of $367$ people, there must be at least two with the same birthdays.
• If an exam is marked on a scale from $0$ to $100$, then from $102$ students, there must be at least two with the same mark.
• If $A$ and $B$ are finite sets with $|A|>|B|$ and $f:A\to B$ is a function, then $f$ is not one-to-one.
• For every $n\in {\mathbb{N}}^{+}$, there is a multiple of $n$ that is not $0$, and has only $0$s and $1$s for its digits. Take any $n\in {\mathbb{N}}^{+}$, consider $n+1$ many numbers. $$1,11,111,...,\stackrel{n+1}{\overbrace{\mathrm{111..1}}}$$
  • Observe that there are $n$ possible different remainders when a natural number is divided by $n$, these are $0,1,...,n-1$.
  • Because there are $n+1$ numbers on the above list, by the pigeonhole principle, there must be two with the same remainder when divided by $n$.
  • Then “the larger of these numbers minus the smaller one”
    • is divisible by $n$ and so is a multiple of $n$
    • has only $0$s and $1$s for its digits

Generalised pigeonhole principle

Generalised pigeonhole principle

The pigeonhole principle states that if $n$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil n/k \rceil$ objects.

Link to original

For example:

• Given $100$ people, there are at minimum $\lceil 100/12\rceil =9$ who were born in the same month.
• If the possible grades for a module are A through F, then among $26$ students, there are always at least $6$ with the same module grade, as $\lceil 26/5\rceil =6$.

Link to original

4-7. Four ways of selecting items

Four ways of selecting items

Say someone is given a bag containing three condiments:

• A: pepper
• B: salt
• C: sugar

In how many ways can they select two sweets? We can follow different principles.

• Order matters means whether we count $AB$ and $BA$ as different elements.
• Repetition allowed means whether we allow elements to pair with themselves, e.g. $AA$, $BB$, $CC$.

Header	Order matters?	Repetition allowed?	Result
A	✅	❌	AB, AC, BA, BC, CA, CB
B	✅	✅	AA, AB, AC, BA, BB, BC, CA, CB, CC
C	❌	❌	AB, AC, BC
D	❌	✅	AA, AB, AC, BB, BC, CC

In summary:

	Order matters permutations	Order doesn’t matter combinations
Repetitions not allowed	$\boxed{n\cdot (n-1)\cdot ...\cdot (n-k+1)}$ $\text{or }\boxed{k!}\text{ if }k=n$	$\left(\begin{array}{c}n\\ k\end{array}\right)$
Repetitions allowed	$n^k$	$\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)=\left(\begin{array}{c}k+n-1\\ k\end{array}\right)$

Where $n$ is the total number of items, $k$ is the number of items we want to select.

Order matters, repetition not allowed

Order matters, repetition not allowed

How many ways can we select $k$ persons from a group of $n$ people to stand in line for a photo shoot? There are:

• $n$ ways to select the first person
• $n-1$ ways to select the second person
• and so on until the $n-(k-1)$ ways to select the $k$th person

So, using the product rule, we find that:

$$\begin{array}{rl}\boxed{n\cdot (n-1)\cdot ...\cdot (n-k+1)}& =\frac{n\cdot (n-1)\cdot ...\cdot (n-k)\cdot ...\cdot 2\cdot 1}{1\cdot 2\cdot ...\cdot (n-k)}\\ & =\frac{n!}{(n-k)!}\end{array}$$

There is a special case when $k=n$:

$$\begin{array}{rl}\frac{k!}{(k-k)!}& =\frac{k!}{0!}\\ & =\frac{k!}{0}\\ & =\boxed{k!}\end{array}$$Link to original

Order matters, repetition allowed

Order matters, repetition allowed

How many words of length $k$ can be formed from the letters of an $n$ letter alphabet?

• There are $n$ ways to select the first letter.
• $n$ ways to select the second.
• $n$ ways to select the $k$th letter.

So by the product rule, the overall number is:

$$\stackrel{k}{\overbrace{n\cdot n\cdot ...\cdot n}}=n^k$$Link to original

Order does not matter, repetition not allowed

Order does not matter, repetition not allowed

How many ways can we select $k$ persons from a group of $n$ people if the order of selection does not matter?

• As seen before, if the order of selection matters, there are $\frac{n!}{(n-k)!}$ ways.
• But then for each set $A$ of $k$ people, we counted the the people in $A$ the number of ways $k$ persons can be ordered. ($k!$)
• So, if the selection order does not matter, then the number of ways is: $$\begin{array}{rl}\frac{\frac{n!}{(n-k)!}}{k!}& =\frac{n!}{(n-k)!\cdot k!}\\ & =\left(\begin{array}{c}n\\ k\end{array}\right)\text{ or }{}_n{C}_k\end{array}$$ This leaves us with the binomial coefficient equation.

Link to original

Order does not matter, repetition allowed

Order does not matter, repetition allowed

Given we have an unlimited supply of $3$ types of fruit:

• A: apples
• O: oranges
• P: peaches

How many ways are there to select $4$ pieces of fruit, if the order of selection does not matter, only the type of fruit / not the individual piece matters?

We could consider a box which can store 4 pieces of fruit, the box can have 3 compartments, each can store one of 3 types of fruit. Compartments are divided by 2 movable dividers that can be shifted depending on how many types of each fruit we want to store. For example:

• 2 apples, 1 orange, 1 peach: $\boxed{AA|O|P}$
• 4 oranges: $\boxed{|OOOO|}$
• 1 apple, 3 peaches: $\boxed{A||PPP}$
• 4 apples: $\boxed{AAAA||}$

So if we have to choose $k$ objects from a set of $n$ objects, with repetition allowed, we need a box with $k$ places for the chosen object and $n-1$ places for the dividers dividing the box into $n$ compartments.

Given any random box: $\boxed{\ast \ast |\ast \ast \ast |\ast ||}$, we have $k+n-1$ places.

The number of ways we can choose our $k$ objects is the number of ways we can distribute the dividers in the box. Out of the $k+n-1$ places, we hace to choose $n-1$ for the dividers. The number of ways of doing this is:

$$\boxed{\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)}=\left(\begin{array}{c}k+n-1\\ k\end{array}\right)$$

This formula should be remembered!

Going back to the example, we find that:

$$\begin{array}{rl}\left(\begin{array}{c}4+3-1\\ 3-1\end{array}\right)& =\left(\begin{array}{c}6\\ 2\end{array}\right)\\ & =\frac{6!}{4!\cdot 2!}\\ & =\frac{6\times 5}{1\times 2}\\ & =15\text{ ways}\end{array}$$Link to original

Link to original