combinatorics

Combinatorics deals with finite sets (i.e. the sets are enumerable) and belongs to the subfield of discrete maths.

Cardinality

The cardinality of a set $A$ is the number of elements in $A$.
We denote the cardinality of $A$ by $|A|$, also denoted by $\text{card}(A)$ or $\#A$.

Link to original

Additivity of cardinality

For two disjoint sets $A,B$, the cardinality of their union is the sum of the cardinalities.

$$A\cap B=\varnothing ⟹|A\cup B|=|A|+|B|$$

For nondisjoint sets, you need the inclusion-exclusion principle to remove the double counting of the intersection.

The product of the cardinalities of two sets is the cardinality of the cartesian product.

$$|A|\cdot |B|=|A\times B|$$

If there is a bijection between two sets, they have the same cardinality.

$A,B,\exists f:A\to B$ bijective $⟹|A|=|B|$

Proof of the product of cardinalities:

$A=\{a_1,\dots a_n\}$, gesucht: $|2^A|$
$f:2^A\mapsto \{0,1{\}}^n=\{0,1\}\times \{0,1\}\times ,\dots ,\times \{0,1\}$ (→ n-tuple)
$$\begin{gathered} B\mapsto (b_1,b_2,\dots ,b_n),b_j\text{cases}0,\text{ if }{a}_j\notin B \\ 1,\text{ else} \end{gathered}$$
If $f$ is injective: $B\subseteq 2^A,B^{\prime }\subseteq 2^A,B\ne B^{\prime }⟹\text{WLOG }\exists j:a_j\in B,a_j\notin B^{\prime }$ (if the resulting images are different, the underlying inputs are different)
$⟹b_j=1,b_j^{\prime }=0⟹f(B)\ne f(B^{\prime })$ (since different inputs lead to different outputs, it’s injective $✓$)
If $f$ is surjective, we need to show: $\forall (b_1,\dots ,b_n)\in \{0,1{\}}^n\exists B\subseteq A:f(B)=(b_1,\dots ,b_n)$
$B=\{a_j\mid b_j=1\}⟹f(B)=(b_1,\dots ,b_n)⟹f\text{ bijective }✓$
$|2^A|=|\{0,1{\}}^n|=2^n$

Sampling $k$ elements from $n$ choices

When order matters:

With replacement: $\#=n^k$
Without replacement: $\#=\frac{n!}{(n-k)!}=n(n-1)\dots (n-k+1)$ (pool gets smaller with each sample)

When order doesn’t matter:
$\#=\frac{n!}{(n-k)!k!}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ (binomial coefficient = “selection from a partial multiset”)

The above but with more words:

With replacement vs. without replacement

$A=\{a_1,\dots ,a_n\}$
(i) Arrangement without constraints “with replacement”: How many ways are there to arrange $k$ elements of $A$?
$\underset{\in A^k}{\underbrace{(x_1,x_2,\dots ,x_k)}},x_i\in A$, Note: $(1,2,3)\ne (2,1,3)$, order matters, as we’re dealing with ordered tuples.
→ $|A^k|=|A{|}^k=n^k$
(ii) Arrangement with unique elements “without replacement”: How many ways are there to arrange $k$ elements of $A$ without repetition?
$(\underset{n}{\underbrace{x_1}},\underset{n-1}{\underbrace{x_2}},\dots ,\underset{n-k+1}{\underbrace{x_k}}),x_i\in A,\forall i\ne j:x_i\ne x_j$
In underbraces $\uparrow$ are the number of possibilities for choosing $x_1,x_2,\dots ,x_k$ → $n(n-1)\dots (n-k+1)=k!\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

(further explanation) $n\cdot (n-1)\cdot (n-2)\dots (n-k+1)$ … starts from $n$ choices, always one less until we reach $k$ terms. We want to know the permutations of $k$ elements, so the product should stop after $k$ terms, hence the $+1$. e.g. for $n=5,k=3$, with … $5\cdot 4\cdot 3$ … without … $5\cdot 4\cdot 3\cdot 2$. Note also, that dividing $n!$ by $(n-k)!$ is is like crossing out the last $n-k$ terms, keeping exactly $k$. So that’s why we can rewrite this with factorials, which looks very similar to the binomial coefficient: $\frac{n!}{(n-k)!}$, just that it doesn’t divide by $k!$ to allow for repetitions.

permutations: How many ways are there to arrange all elements of $A$?

$\pi :A\to A$, bijective permutation function
$f:x_1,x_2,\dots x_n\mapsto (x_1,\dots ,x_n),x_i=\pi (a_i)$
$f:S_A\to \{x\in A^n:\forall i\ne j:x_{i\ne x_j}\}$
$|S_A|=\#(x_1,\dots ,x_n):\forall i\ne j:x_i\ne x_j$ (exactly what we had in (ii) above)
$=n!\left(\genfrac{}{}{0ex}{}{n}{n}\right)=n!$
→ $|A!|=n!$

Permutation notation

$M=\{1,2,3\}$

We can denote the permutation in three ways:
(1) Two rows – the first row is the original order, the second row is the new order:
$\left(\begin{array}{ccc}1& 2& 3\\ \pi (1)& \pi (2)& \pi (3)\end{array}\right)$, e.g.: $\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)⟺1\to 2,2\to 1,3\to 3$
(2) or we just take the second row: $213$,
(3) or we take the cycle notation: $(12)(3)$, i.e. $(1\to 2\to 1)(3\to 3)$.
Each group is its own cycle – no duplicates / loops (else it wouldn’t be bijective which is a requirement for a permutation).

Link to original

^b4a0f0

inclusion-exclusion principle

The inclusion -exclusion principle gives a way to compute the size of the union of multiple non-disjoint sets.

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

→

Inclusion-Exclusion Principle

$n\ge 1$

$$\begin{array}{rl}|\bigcup _{i=1}^n{A}_i|& =\sum _{i=1}^n|A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n-1}|A_1\cap \cdots \cap A_n|\\ & =\sum _{i=1}^n(-1{)}^{i-1}|\bigcap _{j=1}^i{A}_j|\end{array}$$

EXAMPLE

alphabet $\Sigma =\{a,b,c,d,e\}$, set of words (order matters), ${\Sigma }^{\ast }=\{x_1{x}_2\dots x_n|x_i\in \Sigma \}$, empty word $ϵ$.
$W=\{w\in {\Sigma }^{\ast }:w\text{ contains }a,b,c\}$, length $n$
$|W|=?$ … how big is the set of words containing $a,b,c$?
$W={\Sigma }^{\ast }\setminus (W_a\cup W_b\cup W_c)$ … words that don’t contain $a,b,c$
…???

Link to original