# 3 - Bijection Rule, Compliment Rule, Sum Rule, Principle of Inclusion-Exclusion

## Bijections
A function $A \rightarrow B$ is a *bijection* if it is one-to-one (injective) and onto (surjective)

**One-to-one**: For each $y \in B$, there is *at most* one $x \in A$ such that $f(x)=y$

**Onto** For each $y \in B$ there is *at least* one $x \in A$ such that $f(x)=y$

A bijection implies that there is *exactly one* $y \in B$ such that for each $x \in A$ such that $f(x)=y$

What prevents a bijection?

## Bijection Rule
If there exists a bijection $f: A \rightarrow B$ then $|A|=|B|$

### Reminder: Product Rule
$A$ = "the set of possible executions of procedure $P$"
$B=S=$ "the set we want to know the size of."

**Example - Powersets**
$X$ = "a $n$-element set"

$X= \{a,b,c\}$

$P(x)$ = "the set of all subsets of $X$"


**How do we figure this out?**
Let $X=\{x_1, x_2, x_3, ... x_n\}$

For any subset $S \subseteq X$, define a $f(S)=b_1,b_2,b_3,...,b_n$ where $b_i$ is a 0 or 1.

$b_i = 0$ if $x_i \notin S$
$b_i = 1$ if $x_i \in S$


$f$ is a bijection from $P(X)$ to binary strings of length $n$

By the bijection rule
$|P(X)| = |S_n| = 2^n$
$S_n$ = "the set of binary strings of legnth $n$"

If you wanted to prove this using only the product rule, it would be something along the lines of "go through each element in the set and either include it in an element of the resulting powerset or don't"

## The Compliment Rule
We have the set containing all things $U$.
Let $A$ be some set that's not the universe $A \subseteq U$

If $A \subseteq U$ then $|A|=|U| - |U \backslash A|$


**Example**:

A *password* is a string of 8 characters over the alphabet

$\sum$ = $\{a,b,c,...,0,1,2,...,9\}$ that contains at least one digit.

Let $Sigma$ be the set of possible passwords

Let $U$ = all 8-character strings over $\Sigma$

$|\Sigma| = 36$

$|U| = 36^8$ (Proof: Use the product rule with an 8 step procedure, 36 options for each step)

$U \backslash S$ = "String overs $U$ with no digits" = "Strings over $\{a,b,c,....,z\}$"

$|U \backslash S| = 26^8$

$\therefore |S| = |U| - |U \backslash S| = 36^8 - 26^8=2,612,282,842,880$

## The Sum Rule

If $A$ and $B$ are disjoint, then $|A \cup B|=|A|+|B|$

If $A_1, A_2, ... A_n$ are pairwise disjoint then:
$|A_1 \cup A_2 \cup... \cup A_n| = |A_1| + |A_2| + ... + |A_n|$

**Disjoint**: $A \cap B = \emptyset$. There is nothing in $A$ that is also in $B$ and vice versa.

**Example**

A valid password is any string of length 6, 7 or 8 over $\sigma = \{a,b,c,...,z,0,1,2,...9\}$

How many passwords are there?

For each $n \in \{6,7,8\}$ let $S_n$ be the set of valid passwords of length $n$.

$|S_8| = 36^8-26^8$
$|S_7| = 36^7-26^7$
$|S_6| = 36^6-26^6$

$S = S_6 \cup S_7 \cup S_8$
$|S| = |S_6| + |S_7| + |S_8| = 36^6-26^6 + 36^7-26^7 + 36^8-26^8 = 2,684,483,063,360$

## The Principle of Inclusion-Exclusion
For any two sets $A$ and $B$
$|A \cup B| = |A| + |B| - |A \cap B|$

**Example**: Bitstrings of length 17 that start with $010$ or end in $11$


$A$ = "the length 17 bitstrings that start with $010$"
$B$ = "the length 17 bitstrings that end with $11$"

$|A \cup B| = |A| + |B| - |A \cap B|$

$|A| = 2^{14}$
$|B| = 2^{15}$

$|A \cap B| = 2^{12}$

$|A \cup B| = 2^{14} + 2^{15} - 2^{12} = 45,056$

What if there are more than two sets?

For any three sets $A,B,C$
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

**Example**: Bitstrings of length 17 that start with $010$ or end in $11$ or have $10$ at positions 7 & 8 respectively

We've already figured out the size of the first two above.


$C$ = "has 10 at positions 7 & 8 respectively"

$|A| = 2^{14}$
$|B| = 2^{15}$
$|C| = 2^{15}$



###### tags: `COMP2804` `Combinatorics`